Формулы равносильности

Формулы математической логики.

Формулой математической логики называется сложное высказывание, которое получено из элементарных высказываний с использованием логических операций.

Две формулы равносильны, если они принимают одинаковые логические значения на любом наборе значений входящих в формулу элементарных высказываний. Равносильность формул обозначается - A º B.

1) Коммутативность

АVВ º ВVА А&В º В&А

2) Ассоциативность

АV(ВVС) º (АVВ)VС А&(В&С) º (А&В) &С

3) Дистрибутивность

АV(В&С) º (АVВ)&(АVС) А&(ВVС) º (А&В)V(А&С)

4) Идемпотентность

АVА º А А&А º А

5) Поглощение

АV(А&В) º А А&(АVВ) º А

6) Закон де Моргана

º & º V

7) Закон исключающий третьего

АV1 º 1 А&1 º A

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

AVÆ º A A&Æ º Æ

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

º A

10) º 1, º 0

11) A®B ºVB

12) A«B º (A®B)&(B®A)

13) AÅB º A& V &B

14) A | B º º V

15) A¯B º º &

ПРИМЕР

Доказать:

Представление произвольной функции алгебры логики в виде формулы алгебры логики

Пусть - произвольная функция алгебры логики переменных.

Рассмотрим формулу

(2.1)

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

Вместе с тем формула (2.1) содержит в виде логических слагаемых всевозможные конъюнкции указанного вида.

Ясно, что формула (2.1)полностью определяет функцию . Иначе говоря, значения функции и формулы (2.1) совпадают на всех наборах значений переменных . То есть функция

Составление формул по таблице истинности. может быть представлена в виде:

(2.2)

ПРИМЕР Пусть функция имеет следующую таблицу истинности:

Тогда функция может быть определена в следующем виде:

Нетрудно заметить, что для определении функции берутся только те наборы переменных , при которых функция принимает значения 1, что значительно упрощает процедуру определения функции .