Алгебра высказываний Лекция 2

2. Определение высказывания. Таблица истинности для высказываний Определение 1 Переменная А, принимающая два значения – 0 или 1, называется логической (или булевой) переменной. Обозначаться логические переменные будут заглавными латинскими буквами с индексами или без них:

Порядок действий 1)Однотипные операции выполняются в порядке их следования. Например, 2) Отрицание подразумевает скобки. 3) Конъюнкция связывает сильнее, чем дизъюнкция. Например, 4) Дизъюнкция связывает сильнее, чем импликация. Например, 5) Импликация связывает сильнее, чем эквивалентность. Например,

Примеры 1)Избавиться от лишних скобок Ответ 2)Расставить порядок действий

Определение 2 Таблица истинности для высказывания имеет вид A1A1 A2A2 …A n-1 AnAn F(A 1, A 2,…, A n-1, A n ) 00…00F(0,0,…,0,0) 00…01F(0,0,…,0,1) ……………… 11…10F(1,1,…,1,0) 11…11F(1,1,…,1,1) Если высказывание F построено из логических переменных, то будем обозначать это высказывание: Теорема Наборов длины n из 0 и 1 существует

3. Равносильные высказывания. Определение 1 Высказывания F(A 1,A 2,…,A n ) и G(A 1,A 2,…,A n ) называются равносильными (или просто равными), если для любого набора имеет место равенство: Обозначим Другими словами, два высказывания равны, если у них совпадают таблицы истинности.

Примеры Доказательство AB

Основные логические тождества Идемпотентные законы: Коммутативные законы: Ассоциативные законы: 1) 2) 3) 4) 5) 6) 7) 8)

Законы Моргана: Закон двойного отрицания: Закон противоречия: Закон исключенного третьего: 9) 10) 11) 12) 13) 14) 15) Дистрибутивные законы: Без названия: 16) 17)

Законы поглощения: Доказательство 16) 17) 18) 19)

Тождества, содержащие константы: