ФОРМЫ МЫШЛЕНИЯ АЛГЕБРА ЛОГИКИ ПОСТРОЕНИЕ ТАБЛИЦ ИСТИННОСТИ. ЗАКОНЫ

ОСНОВЫ КОМПЬЮТЕРА.

вычислительной технике
Логика
Аристотель (384-322 до н.э.). Основоположник формальной логики (понятие, суждение,

умозаключение).

Джордж Буль (1815-1864). Создал новую область науки - Математическую логику (Булеву алгебру или Алгебру высказываний).

Логика – это наука о формах и способах мышления.
Первые учения о формах и способах мышления возникли в Древнем Китае и Индии. Основоположником формальной логики является Аристотель.

это форма мышления, которая выделяет существенные признаки предмета или класса

предметов, позволяющие отличать их от других.

Высказывание - это формулировка своего понимания окружающего мира. Высказывание является повествовательным предложением, в котором что-либо утверждается или отрицается. По поводу высказывания можно сказать, истинно оно или ложно.

Умозаключение - это форма мышления, с помощью которой из одного или нескольких суждений может быть получено новое суждение.

и т.д.
Общие понятия: красота, металл, доброта, глупость, лес, коллектив и

т.д.
Абстрактные понятия: вес, жесткость, цвет, вселенная, человечество и т.д.
Конкретные понятия: круг, дом, пламя, битва и т.д.

Примеры понятий:

Рядом с названием предмета перечислены его признаки. Какие из них являются существенными для данного предмета?
А) Ученик - высокий; умный; одет в форму; на спине - ранец; посещает школу; любит книги; много знает; овладевает знаниями; учится; веселый.

Б) Ромашка - полевой цветок; имеет белые лепестки и желтую середину; лекарственное растение; неприхотливый цветок; цветок, растущий у дороги.

Существенными называются такие признаки, каждый из которых, взятый отдельно, необходим, а все вместе достаточны, чтобы с их помощью отличить данный предмет от всех остальных и сделать обобщение, объединив однородные предметы в множество.

его признаков. Среди признаков предмета есть существенные и второстепенные. Содержание

понятия может меняться в зависимости от знаний, от точки зрения и т.д. Например, для обычного человека содержанием понятия "вода" являются следующие ее признаки: прозрачная, жидкая, безвкусная, ее пьют, утоляя жажду. Для химика вода - вещество, содержащее водород и кислород, компонент многих реакций.
Объем понятия - множество предметов, к которым прилагается понятие.
Например, объем понятия "четырехугольник": параллелограмм, ромб, прямоугольник, квадрат, трапеция. Между объемом и содержанием понятия существует важное соотношение: при увеличении содержания понятия уменьшается его объем и наоборот.
Расположите и запишите понятия в порядке расширения их объемов: насекомое, живое существо, комар.

Понятие

Комар, насекомое, живое существо.

можно однозначно определить как истинное или ложное.
В русском языке высказывания

выражаются повествовательными предложениями:
Земля вращается вокруг Солнца.
Москва - столица.

Побудительные и вопросительные предложения высказываниями не являются.
Без стука не входить!
Откройте учебники.
Ты выучил стихотворение?

Высказывание

Но не всякое повествовательное предложение является высказыванием:
Это высказывание ложное.

пришел?
У треугольника 5 сторон.
Как пройти в библиотеку?
Переведите число в десятичную

систему.
Запишите домашнее задание

зависит от значений входящих в него переменных.
Высказывания
Высказывание

переход от сведений, которыми мы располагаем до рассуждения (посылок или

условий), к выводам. Правильный способ умозаключений из истинных посылок всегда ведет к истинным выводам.

Общее

Частное

Рассуждение

высказываний.
В алгебре логики высказывания обозначают буквами и называют логическими переменными.

Если высказывание истинно, то значение соответствующей ему логической переменной обозначают единицей (А = 1), а если ложно - нулём (В = 0).
0 и 1 называются логическими значениями.

Алгебра логики

если никакая его часть сама не является высказыванием.
Сложные (составные)

высказывания строятся из простых с помощью логических операций.

Логические операции имеют следующий приоритет:
инверсия, конъюнкция, дизъюнкция, импликация, эквивалетность

новое высказывание, являющееся истинным тогда и только тогда, когда оба

исходных высказывания истинны.
Другое название: логическое умножение.
Обозначения:  , , &, И.

Логические операции

Таблица истинности:

Графическое представление

А&В

соответствие новое высказывание, являющееся ложным тогда и только тогда, когда

оба исходных высказывания ложны.
Другое название: логическое сложение.
Обозначения: V, |, ИЛИ, +.

Логические операции

Таблица истинности:

Графическое представление

А V В

новое высказывание, значение которого противоположно исходному.
Другое название: логическое отрицание.
Обозначения: НЕ,

¬ , ¯ .

Логические операции

Таблица истинности:

Графическое представление

операции
Импликация – это логическая операция, ставящая в соответствие каждым двум

простым высказываниям составное высказывание, являющееся ложным тогда и только тогда, когда условие (первое высказывание) истинно, а следствие (второе высказывание) ложно.

Таблица истинности:

Графическое представление

соответствие каждым двум высказываниям составное высказывание, являющееся истинным тогда и

только тогда, когда оба исходных высказывания одновременно истины или одновременно ложны.

В естественном языке – «Тогда и только тогда и в том и только том случае»;

Обозначение – ↔

Таблица истинности:

Графическое представление

в выражении
подсчитать общее число логических операций в выражении
установить последовательность выполнения

логических операций

определить число столбцов в таблице

заполнить шапку таблицы, включив в неё переменные и операции

определить число строк в таблице без шапки: m =2n

выписать наборы входных переменных

провести заполнение таблицы по столбцам, выполняя логические
операции в соответствии с установленной последовательностью

= 4.
Приоритет операций: &, V
Пример построения таблицы истинности

= B V A
A&(BVC)= (A&B) V (A&C)
AV(B&C) = (AVB)&(AVC)
(A &

B) & C = A & ( B & C)

(A V B) V C =A V ( B V C)

Переместительный

Сочетательный

Распределительный

Закон двойного
отрицания

A & Ā = 0

A V Ā = 1

A & 0=0; A &1 = A

A V 0 = A; A V 1 = 1

A & A = A

A V A = A

Закон исключения
третьего

Закон повторения

Законы операций
с 0 и 1

Законы общей
инверсии

Свойства логических операций

= (A v B) & (A v C).
Доказательство закона
Умножаем В

на С и выводим результат.

0

0

0

0

0

0

1

1

Складываем А и В и выводим результат.

0

0

0

1

1

1

1

1

Складываем А и (В&С) и выводим результат.

0

0

1

1

1

1

1

1

Складываем А и C и выводим результат.

0

0

1

1

1

1

1

1

Умножаем (АvB) на (AvC )и выводим результат.

0

0

0

1

1

1

1

1

Равенство выделенных столбцов доказывает распределительный закон.

один из мальчиков нечаянно разбил любимую бабушкину вазу.
Решение логических задач
На

вопрос, кто разбил вазу, они дали такие ответы:
Серёжа: 1) Я не разбивал. 2) Вася не разбивал.
Вася: 3) Серёжа не разбивал. 4) Вазу разбил Коля.
Коля: 5) Я не разбивал. 6) Вазу разбил Серёжа.

Бабушка знала, что один из её внуков (правдивый), оба раза сказал правду; второй (шутник) оба раза сказал неправду; третий (хитрец) один раз сказал правду, а другой раз - неправду. Назовите имена правдивого, шутника и хитреца.
Кто из внуков разбил вазу?

=«Серёжа разбил вазу».
Представим в таблице истинности высказывания каждого мальчика.

Так как ваза разбита одним внуком, составим не всю таблицу, а только её фрагмент, содержащий наборы входных переменных: 001, 010, 100.

Исходя из того, что знает о внуках бабушка, следует искать в таблице строки, содержащие в каком-либо порядке три комбинации значений: 00, 11, 01 (или 10). Это первая строка.
Вазу разбил Серёжа, он - хитрец. Шутником оказался Вася. Имя правдивого внука - Коля.

 Y = ¬X v Y
2). Преобразуем ¬X:
Аналогично для Y:
XY=
Справка

Андрей, Боря, Сережа и Володя заняли первые четыре места. Но

когда девочки стали вспоминать, как эти места распределились между победителями, то мнения разошлись:
Даша: Андрей был первым, а Володя – вторым.
Галя: Андрей был вторым, а Борис – третьим.
Лена: Боря был четвертым, а Сережа – вторым.
Известно, что каждая девочка в одном утверждении ошиблась, а в другом была права. Кто из мальчиков какое место занял?

Введем обозначения:
А1 – Андрей первый, В2 – Володя второй, А2 – Андрей второй, Б3 – Борис третий, Б4 – Борис четвертый, С2 – Сережа второй

утверждении одно высказывание истинно, а другое ложно:
Запишем это условие для

высказываний каждой девочки:

Так как один и тот же человек не может занять разные места, и разные спортсмены не могут находиться на одном месте, получим из первых 2-х скобок:

Полученный результат умножим логически на 3-ю скобку:

А1=1; Б3=1; С2=1; => В4=1

Ответ: Андрей – первый, Сергей – второй, Борис – третий, Володя - четвертый

на выходе сигнал, являющийся значением одной из логических операций, называется

логическим элементом.

Базовые логические элементы реализуют три базовые логические операции:
логический элемент «И» (конъюнктор) – логическое умножение;
логический элемент «ИЛИ» (дизъюнктор) – логическое сложение;
логический элемент «НЕ» (инвертор) – логическое отрицание.
Любая логическая операция может быть представлена в виде комбинации трех базовых, поэтому любые устройства компьютера, производящие обработку и хранение информации, могут быть собраны из базовых логических элементов.
Логические элементы компьютера оперируют с сигналами, представляющими собой электрические импульсы.
Есть импульс – логическое значение сигнала 1, нет импульса – значение 0.

Таким образом, F = A & B.
Какой сигнал должен быть

на выходе при каждом возможном наборе сигналов на входах?

Решение. Все возможные комбинации сигналов на входах А и В внесём в таблицу истинности. Проследим преобразование каждой пары сигналов при прохождении их через логические элементы и запишем полученный результат в таблицу. Заполненная таблица истинности полностью описывает рассматриваемую электронную схему.

В инвертор поступает сигнал от входа В.

Анализ электронной схемы

такие элементы как сумматоры. Они позволяют складывать двоичные числа.
Сложение в

пределах одного разряда (без учета возможной пришедшей единицы из младшего разряда) можно реализовать схемой, которая называется полусумматором. У полусумматора два входа (для слагаемых) и два выхода (для суммы и переноса).
В отличие от полусумматора сумматор учитывает перенос из предыдущего разряда, поэтому имеет не два, а три входа.

?

хранить и считывать информацию.
Каждый триггер хранит 1 бит информации,

т.е он может находиться в одном из двух устойчивых состояний — логический «0» или логическая «1».
Триггер способен почти мгновенно переходить из одного электрического состояния в другое и наоборот.

Триггер

Логическая схема триггера выглядит следующим образом:
Входы триггера расшифровываются следующим образом — S (от английского Set - установка) и R (Reset - сброс). Они используются для установки триггера в единичное состояние и сброса в нулевое. В связи с этим такой триггер называется RS-триггер.
Выход Q называется прямым, а противоположный — инверсный. Сигналы на прямом и инверсном выходах, конечно же, должны быть противоположны.

R=0. Тогда независимо от состояния другого входа, который подсоединен к

выходу Q (иначе говоря, вне зависимости от предыдущего состояния триггера), верхний по схеме элемент ИЛИ-НЕ получит на выходе 0 (результат ИЛИ равен 1, но его инверсия - 0). Этот нулевой сигнал передается на вход другого логического элемента, где на втором входе R тоже установлен 0. В итоге после выполнения логических операций ИЛИ-НЕ над двумя входными нулями этот элемент получает на выходе 1, которую возвращает первому элементу на соответствующий вход. Последнее обстоятельство очень важно: теперь, когда на этом входе установилась 1, состояние другого входа (S) больше не играет роли. Иными словами, если даже теперь убрать входной сигнал S, внутреннее распределение уровней сохранится без изменения.

Поскольку Q = 1, триггер перешел в единичное состояние, и, пока не придут новые внешние сигналы, сохраняет его. Итак, при подаче сигнала на вход S триггер переходит в устойчивое единичное состояние.

При противоположной комбинации сигналов R = 1 и S = 0 вследствие полной симметрии схемы все происходит совершенно аналогично, но теперь на выходе Q уже получается 0. Иными словами, при подаче сигнала на R-триггер сбрасывается в устойчивое нулевое состояние.
Таким образом окончание действия сигнала в обоих случаях приводит к тому, что R = 0 и S = 0.

Триггер