Определение тождественности логических функций

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

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

Пример 7.Проверить тождественность логических функций:

Решение:

А. Упрощение функции F.

Применяем закон отрицания и перемножаем скобки, т.е. .

Во второй скобке конъюнкции и склеиваются, поэтому получаем:

Переменная поглощает конъюнкцию , что дает:

или .

Функция F оказалась записанной в СДНФ, так как содержит конъюнкции одинакового ранга, и в них входят все переменные, от которых она зависит.

Б. Преобразование функции f .

. Функция f также записана в СДНФ.

Так как СДНФ функций F и f не совпадают, то они не являются тождественными.

В. Преобразование функции P.

. Получена СДНФ функции P.

Функции F и P являются тождественными, так как имеют одинаковые СДНФ.

Пример 8.Проверить тождественность логических функций F и f.

.

принимает единичные значения на наборах 2, 3.

Решение:

А. Упрощение функции F.

Применяется закон отрицания: .

Во второй скобке переменная поглощает конъюнкцию , что приводит к следующему результату: .

Во второй скобке используется правило свертки, и затем скобки перемножаются:

.

Б. Получение СДНФ функции F.

.

В. Получение СДНФ функции f.

Так как функции f принимает единичные значения на наборах 2 и 3, то ее СДНФ будет иметь вид .

Функции F и f имеют одинаковые СДНФ, следовательно, они тождественны.

Пример 9.Проверить тождественность логических функций:

и .

Решение:

Функция f имеет следующую минимальную форму: .

А. Упрощение функции F:

- перемножение скобок

- исключение лишней конъюнкции из группы ;

- исключение лишней конъюнкции yz из группы .

В результате получаем: .

Упрощенная форма функции F и минимальная форма функции f не совпадают. Однако это не значит, что функции не тождественны. Для окончательного вывода нужно получить СДНФ обеих функций.

Б. Получение СДНФ функции F.

После удаления повторяющихся конъюнкций получаем:

В. Получение СДНФ функции f.

.

Функции F и f имеют одинаковые СДНФ и принимают единичные значения на одних и тех же наборах 0, 1, 2, 3, 4, 5, 6, 7. Эти функции тождественны. Так как минимальные формы функций не совпадают, то можно сделать вывод, что для функции F была получена тупиковая форма.

Пример 10.Три множества A={a, b, c}, B={0, 1}, C={1, 5, c} заданы перечислением элементов. Определить множество D, являющееся решением D=(A B) C.

1) {c, 1};

2) {a, b, 1};

3) {c, 1, 5};

4) {1};

5) {Ø}.

Решение:

Построим множество D = (A B) C. Выполним операции по шагам.

А. A B = {a, b, c} {0, 1} = {Ø}, т.к. нет общих элементов.

Б Б. (A B) C = {Ø} {1, 5, c} = {Ø},, т. к. нет общих элементов.

Ответ:5).

Пример 11.. Укажите, при каких значениях x, y, p истинно следующее выражение:

(p и (x-1 < y) или не (x >= y)).

1) x=7, y=6, p=нет;

2) x=7, y=6, p=да;

3) x=7, y=7, p=нет;

4) x=4, y=6, p=да;

5) x=6, y=4, p=да.

Решение:

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

2 1 5 4 3

(p и (x-1 < y) или не (x >= y)).

Б. Составим таблицу истинности для каждого варианта ответа.

Ответ:4)

Пример 12. Укажите, при каких значениях x, y, z, ложно следующее выражение: (не z или (y и x)) и (не x или y).

1) x=1, y=1, z=1;

2) x=0, y=1, z=0;

3) x=1, y=0, z=1;

4) x=0, y=0, z=0;

5) x=1, y=1, z=0.

Решение:

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

2 3 1 6 4 5

(не z или (y и x)) и (не x или y).

Б. Составим таблицу истинности для каждого варианта ответа.

Ответ:3)