1) р.
Коммутативность:
2) р q q р.
3) .
Ассоциативность:
4) (р q) r р (q r).
5) () r р (q r).
Дистрибутивность:
6) р (q r). р r.
7) р (q r) (р q) (р r).
Законы Де-Моргана:
8) .
9) .
Поглощение:
10) р р р.
11) р р р.
Операции с 0 и 1
12) р 0 0.
13) р 1 р.
14) р 0 р.
15) р 1 1.
Связь с отрицанием
16) р 0.
17) р 1.
Связь импликации и эквиваленции с другими операциями
18) q.
19) () ().
Доказательство этих равносильностей происходит путем построения таблиц истинности.
Используются равносильности при преобразованиях формул.
Пример преобразований с использованием равносильностей.:
r (снимаем эквиваленциию по 19)
(() r )(r ()) снимаем импликации по 18)
( r)( q) (по законам де Моргана)
( r)( q) (снимаем двойные отрицания по 1)
(р r)(q q) (в первой скобке выносим за скобку по 6, во второй скобке по 11) (р ) (q ) (по 6)
(р ) (q ) (по 16)
(р ) (0 ) (по 14)
(р ) ( ) (по 6)
р р (по 10 и 16)
р 0 (по 14 и 6)
(р 1) 1 .
Решение логических уравнений.
Используя определения логических операций, мы можем решать логические уравнения. Общий принцип решения уравнения:
1) Задается некоторая формула, равная или 1, или 0.
2) Определяем какую операцию задает это уравнение, и затем в соответствии с определением этой операции данное уравнение сводится к системе или совокупности уравнений.
3) Для каждого из этих уравнений повторяем действия 1 и 2 пока не дойдем до значений элементарных высказываний, а затем каждой из систем производим сопоставление полученных значений.
Например: q р q =0.
Решение:
Импликация ложна, когда
Это приводит нас к системе
т.к.; q=1, то , т.е. r=1.
Получим решение
Замечание1. Левую часть уравнения можно преобразовать, а затем решать получившееся уравнение. Иногда это упрощает дело.
Замечание2. Если уравнение имеет вид Ф!=Ф2, то следует рассматривать две
системы и
Виды формул.
Формула называется тождественно истинной (тавтологией), если она принимает значение 1 при любых наборах значений высказываний, входящих в эту формулу.
Формула называется тождественно ложной, если она принимает значение 0 при любых наборах значений высказываний, входящих в эту формулу.
Если формула не тавтология и не тождественно ложная, то она называется выполнимой.
Пример: Установить вид формулы ()
Решение:
Построим таблицу истинности формулы:
р | q | () | () | |||
Ответ: формула- тавтология.
Связь равносильности () и эквиваленции().
Терема. Две формулы и равносильны тогда и только тогда, когда формула - тавтология.
Доказательство:
Достаточность:
Пусть 1. Это означает, что при любых наборах высказывательных переменных, входящих в эквиваленцию, формулы и принимают одинаковые значения. По определению равносильности .
Необходимость:
Пусть . Это означает, что и принимают одинаковые значения при любых наборах высказывательных переменных. Но тогда по определению эквиваленции =1, т.е. является тавтологией.
Нормальные формы.
Если формула содержит только элементарные высказывания и (или) их отрицания, между которыми стоит знак дизъюнкции (), то эту формулу будем называть элементарной суммой.
Например: = р q .
Если формула является конъюнкцией () элементарных высказываний и (или) их отрицаний, то она называется элементарным произведением.
Например: = рq