Элементы алгебры логики

Элементы алгебры логики

Истина

0

Ложь

1

1

0

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

Алгебра логики – наука об операциях, выполняемые над высказываниями. Она изучает логические операции над высказываниями с точки зрения их истинностного значения (истина, ложь).

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

Создателем алгебры логики является Джордж Буль, английский математик и логик, положивший в основу своего учения аналогию между алгеброй и логикой.

Дж. Буль

(1815 – 1864)

Логические выражения

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

Простое логическое выражение состоит из одного высказывания и не содержит логических операций. В простом логическом выражении возможен только один результат – либо «истина», либо «ложь». Обозначается буквами латинскими буквами A, B, C и т. д.

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

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

«Шесть минус три равно три», «Париж – столица Франции» - истинные высказывания , «пять больше семи», «Луна – это звезды» - ложные высказывния.

Определите значения истинности для следующих высказываний

Лед — твёрдое состояние воды.

Треугольник — это геометрическая фигура.

Париж — столица Китая.

Как пройти к вокзалу?

Иди к доске .

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

Обозначения результатов логических утверждений

1

True

Истина

Да (истинно)

0

False

Ложь

Нет (ложно)

Логическая переменная

Логическая переменная  — это переменная, которая обозначает любое высказывание и может принимать логические значения «истина» или «ложь».

Выражения A и B – логическая конструкция (функция), где А, B – операнды (аргументы), «и» - операция (действие).

Операнд – аргумент операции, т.е. то, над чем выполняется операция.

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

Унарная (одноместная) операция – операция, которая применяется к одному операнду.

• Изменение знака числа. К А применим операцию изменения знака, получим ( -А ).

Бинарная (двуместная) операция – операция, которая выполняется над двумя операндами. Бинарную операцию принято обозначать знаком действия, который ставится между операндами. Такая форма записи называется инфиксной .

• Сложение ( А + В ), вычитание ( А – В ), умножение ( А*В )

Тернарная (трёхместная) операция – операция, которая выполняется над тремя операндами.

• Среднее арифметическое трёх чисел, смешанное произведение векторов.

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

Таблицы истинности – таблицы с результатами каждой логической операции.

https://resh.edu.ru/subject/lesson/5426/main/163624/

Алгоритм построения таблицы истинности

1. Подсчитать n — число переменных в логическом выражении.

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

3. Установить последовательность выполнения логических операций с учётом скобок и приоритетов.

4. Определить число столбцов в таблице: число переменных + число операций.

5. Заполнить шапку таблицы, включив в неё переменные и операции в соответствии с последовательностью, установленной в пункте 3.

6. Определить число строк в таблице (не считая шапки таблицы) по формуле m = 2 n , где n — количество переменных.

7. Выписать наборы входных переменных с учётом того, что они представляют собой целый ряд n-разрядных двоичных чисел от 0 до 2 n –1.

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

Логическое отрицание (Логическое НЕ)

Логическое отрицание, или инверсия – унарная операция, в результате которой из данного высказывания (например А) получается новое высказывание (не А ), которое называется отрицанием исходного высказывания.

Например : «Катя получила двойку», после применения отрицания получим: «Катя не получила двойку».

Если на входе схемы отправить значение 0, то на выходе будет значение 1 (У данной схемы один вход и один выход, операция унарная.

Обозначается : , не А, not A

Читается : «Не А»

Таблица истинности инверсии

• Высказывание А «10 – простое число» ложно.
• Высказывание «10 не простое число» истинно.

Логическое умножение (Логическое И)

Логическое умножение, или конъюнкция – бинарная операция, соединяющая два высказывания и более с помощью связки «и» (например, «А и В»).

Например : «Этот треугольник равнобедренный и прямоугольный».

На вход подаются два значения – А, В, на выходе будет значение конъюнкции этих двух входящих.

Например: подали на вход значения 0 и 1, выполнится 0 & 1, и на выходе получим 0.

Обозначается : А ^ B, A & B, A * B, A x B, А и В, А and В.

Читается : «А и В»

Таблица истинности конъюнкции

Конъюнкция истинна только тогда, когда оба высказывания А, В истинны.

Логическое сложение (Логическое ИЛИ)

Логическое сложение, или дизъюнкция – бинарная операция, соединяющая два высказывания и более с помощью связки «или» (например, «А или В»).

Например : «Число x делится на 3 или на 5 ».

На вход подаются два значения – А, В, на выходе будет значение дизъюнкции этих двух входящих.

Например : подали на вход значения 0 и 1, выполнится 0  1, и на выходе получим 1.

Обозначается : А  B, A + B, A | В, A или B, А or В.

Читается : «А или В»

Таблица истинности дизъюнкции

Высказывание будет истинным, если выполняются оба условия или хотя бы одно из условий.

Логическое следование (импликация)

Логическое следование, или импликация – логическая операция, соединяющая два высказывания с помощью связки «если … то ….»

Например : «Если четырёхугольник – квадрат, то в него можно будет вписать окружность».

Обозначается : А  В, А  В

Читается : «Если А, то В», «из А следует В», «А влечет В», «А имплицирует В»

Импликация – сокращенная запись для выражения (  B ). При решении задач можно уверенно заменять в выражении импликацию этой записью.

Результат операции ложен только тогда, когда предпосылка есть истина, а следствие ложь.

Таблица истинности импликации

Операция связывает два простых выражения, из которых первое является условием, а второе - следствием. Результат операции ложен только тогда, когда предпосылка есть истина, а следствие - ложь.

Например : «Если 3*3 = 9 (А), то Солнце – планета (В)», результат импликации А  В – ложь

Строгая дизъюнкция

Строгая дизъюнкция, т.е. исключающее ИЛИ – бинарная операция, соединяющая два высказывания с помощью связки «или», употребленной в исключающем смысле.

Например : «Этот треугольник тупоугольный или остроугольный». Обозначается : А  В, А   В, А or В

Читается : «Либо А, либо В»

Высказывания истинно, если выполняется одно из условий.

Таблица истинности операции

«Исключающее ИЛИ»

«Исключающее ИЛИ (высказывания А  В) истинно только тогда, когда высказывания А и В имеют различные значения»

Эквивалентность

Эквивалентность, или двойная импликация – бинарная операция, позволяющая из двух высказываний А и В получить новое высказывание А = В.

Например : «Треугольник будет прямоугольным тогда и только тогда, когда один из его углов равен ».

Обозначается : А  В, А  В, А В

Читается : «А эквивалентно В», «А тогда и только тогда, когда В», «А то же самое что и В», «А равносильно В»

Эквивалентность – сокращенная запись для выражения (  B )  (  B). При решении задач можно уверенно заменять в выражении эквивалентность этой записью.

Таблица истинности эквивалентности

Операция эквивалентности противоположна исключающему «ИЛИ» и имеет результат «истина» тогда и только тогда, когда значения переменных совпадают.

Приоритеты логических связок

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

Например : 2 + 2 * 2 не то же самое, что (2+2) * 2.

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

Пример

¬А ∧ С v (A ⊕ В) ∧ В

Правила приоритетов для логических связок

Выражение в скобках

Логическое НЕ

Логическое И

Логическое ИЛИ

Импликация

Эквивалентность

Пример

1

3

2

5

4

А v В  С & D  ¬А

Порядок выполнения логических операций в сложном логическом выражении

1. инверсия

2. конъюнкция

3. дизъюнкция

4. импликация

5. эквивалентность

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

Основные законы логики

Законы логики выражают необходимые условия для правильного последовательного мышления.

Название закона, формула

Закон тождества:

Содержание

A = A

Любое высказывание тождественно самому себе

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

А & ¬А = 0

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

Высказывание не может быть истинно и ложно одновременно

А \/ ¬А = 1

В конкретный момент времени высказывание может иметь истинное или ложное значение, третье исключено

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

¬(¬А) = А

При двойном отрицании исходного суждения в итоге получится оно же

Для формулы A /\ (B \/ ¬ B /\ ¬ C) постройте таблицу истинности.

A

B

C

1.

A /\ (B \/ ¬ B /\ ¬ C)

2.

Количество логических операций в формуле: 5.

3

2

5

1

4

A /\ (B \/ ¬ B /\ ¬ C)

3.

4.

Количество столбцов: 3+5=8

5.

Количество строк: 8+1 = 9

Для формулы A /\ (B \/ ¬ B /\ ¬ C) постройте таблицу истинности.

А

0

В

0

С

0

0

0

0

¬В

1

1

1

¬С

0

1

0

1

1

¬В /\¬С

1

0

1

0

В \/ ¬В /\¬С

1

0

1

0

1

0

0

1

A/\(B\/ ¬B /\¬C)

1

0

0

1

1

0

1

0

0

1

0

1

1

1

1

0

0

0

1

0

0

1

1

0

0

0

1

1

1

0

0

0

1

0

0

1

1

1