Основы логики Алгебра высказываний

Основы логики Алгебра высказываний Автор: Сергеев Евгений Викторович МОУ СОШ №4 г. Миньяра Челябинской области sergeev73@mail.ru http://shk4-minyar.ucoz.ru

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

Логические переменные Логические переменные – простые высказывания, содержащие только одну мысль. Обозначаются буквами латинского алфавита: A, B, C… Логические переменные могут принимать лишь два значения: «ИСТИНА» (1) или «ЛОЖЬ» (0)

Логические переменные Например, два простых высказывания: А = «2  2 = 4» истина (1) В = «2  2 = 5» ложь (0) являются логическими переменными А и В

В алгебре высказываний высказывания обозначаются именами логических переменных, которые могут принимать лишь два значения: «ИСТИНА» (1) или «ЛОЖЬ» (0)

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

Составные высказывания Высказывания, состоящие из нескольких простых суждений и содержащие в себе более, чем одну простую мысль, называются логическими функциями Обозначаются F(A,B,C…) Также могут принимать значения «ИСТИНА» или «ЛОЖЬ» в зависимости от того, какие значения имеют входящие в их состав логические переменные и от действий над ними

Логические операции Конъюнкция (логическое умножение, «И») Дизъюнкция (логическое сложение, «ИЛИ») Инверсия (логическое отрицание, «НЕ») Импликация (логическое следование, «Если А, то В») Эквивалентность (логическое равенство, «А тогда и только тогда, когда В»)

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

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

Конъюнкция. Определите истинность логической функции «2  2 = 5» И «3  3 = 10» «2  2 = 5» И «3  3 = 9» «2  2 = 4» И «3  3 = 10» «2  2 = 4» И «3  3 = 9» Истинна только функция (4)

Запись конъюнкции на формальном языке алгебры высказываний F(A,B) = A & B или F(A,B) = A  B Также может встретиться запись, типа: F(A,B) = A * B или F(A,B) = A and B

Значение логической функции определяется по ее таблице истинности Таблица истинности показывает какие значения принимает логическая функция при всех возможных значениях логических переменных

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

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

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

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

Дизъюнкция. Определите истинность логической функции «2  2 = 5» ИЛИ «3  3 = 10» «2  2 = 5» ИЛИ «3  3 = 9» «2  2 = 4» ИЛИ «3  3 = 10» «2  2 = 4» ИЛИ «3  3 = 9» Ложна только функция (1), остальные истинны

Запись дизъюнкции на формальном языке алгебры высказываний F(A,B) = A  B Также может встретиться запись, типа: F(A,B) = A + B или F(A,B) = A or B

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

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

Присоединение частицы «НЕ» к высказыванию называется операцией логического отрицания, или инверсией

Логическое отрицание (инверсия) делает истинное высказывание ложным, а ложное – истинным [логическая отрицательная единица, перевертыш]

Инверсия Пусть A = «2  2 = 4» – истинное высказывание, тогда F(A) = «2  2 ≠ 4» – ложное высказывание

Запись инверсии на формальном языке алгебры высказываний F(A) = ¬A или F(A) = Ā Также может встретиться запись, типа: F(A) = not А

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

Таблицы истинности основных логических функций

Дополнительные логические функции Импликацию и эквивалентность можно выразить через конъюнкцию, дизъюнкцию и отрицание, поэтому их называют дополнительными логическими функциями: Импликация: А → В = ¬A  В или А  В = ¬A  В или А  В = ¬A  В Эквивалентность: А ↔ В = (¬A  В)  (¬B  A) или А  В = (¬A  В)  (¬B  A) или А ≡ В = (¬A  В)  (¬B  A)

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

Импликация Импликация ложна тогда и только тогда, когда условие истинно, а следствие ложно Пример: Если выучишь материал, то сдашь зачет Это высказывание ложно только тогда, когда материал выучен, а зачет не сдан, т.к. сдать зачет можно и случайно, например если попался единственный знакомый вопрос или удалось воспользоваться шпаргалкой

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

Эквивалентность Эквивалентность – это логическая операция, объединяющая два простых высказывания в одно составное и которое является истинным тогда и только тогда, когда оба исходных высказывания одновременно либо истинны, либо ложны.

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

Переместительный Дизъюнкция: X  Y ≡ Y  X Конъюнкция: X  Y ≡ Y  X

Сочетательный Дизъюнкция: X  (Y  Z) ≡ (X  Y)  Z Конъюнкция: X  (Y  Z) ≡ (X  Y)  Z

Распределительный Дизъюнкция: X  (Y  Z) ≡ X  Y  X  Z Конъюнкция: X  (Y  Z) ≡ (X  Y)  (X  Z)

Правила де Моргана Дизъюнкция: ¬(X  Y) ≡ ¬X  ¬Y Конъюнкция: ¬(X  Y) ≡ ¬X  ¬Y

Идемпотенции Дизъюнкция: X  X ≡ X Конъюнкция: X  X ≡ X

Поглощения Дизъюнкция: X  (X  Y) ≡ X Конъюнкция: X  (X  Y) ≡ X

Склеивания Дизъюнкция: (X  Y)  (¬X  Y) ≡ Y Конъюнкция: (X  Y)  (¬X  Y) ≡ Y

Переменная со своей инверсией Дизъюнкция: X  ¬X ≡ 1 Конъюнкция: X  ¬X ≡ 0

Операция с константами Дизъюнкция: X  0 ≡ X, X  1 ≡ 1 Конъюнкция: X  0 ≡ 0, X  1 ≡ X

Двойного отрицания ¬(¬X) ≡ X

Порядок действий Действия в скобках Отрицание Конъюнкция Дизъюнкция Импликация Эквивалентность