Контрольная работа по математической логике и теории алгоритмов на тему Используя таблицу истинности, установить эквивалентность функций в формуле

1. Используя таблицу истинности, установить эквивалентность функций в формуле.
.
Решение.
Построим таблицу истинности левой части.
.

0 0 0 1 0 1 1 1 1 0 1 0 1
0 0 1 1 0 1 0 1 0 0 0 1 0
0 1 0 0 0 1 1 1 1 0 1 0 1
0 1 1 0 0 1 0 1 0 0 0 1 0
1 0 0 1 0 1 1 0 0 0 0 1 0
1 0 1 1 1 0 0 0 0 0 0 0 1
1 1 0 0 0 1 1 0 0 0 0 1 0
1 1 1 0 0 1 0 0 0 1 1 0 1
Построим таблицу истинности правой части.
.













0 0 0 1 1 1 1 1 0 0 1 1
0 0 1 1 0 1 1 0 1 0 0 0
0 1 0 0 1 1 1 1 0 0 1 1
0 1 1 0 1 1 1 0 1 0 0 0
1 0 0 1 1 1 0 1 1 1 0 0
1 0 1 1 0 0 0 0 0 1 0 1
1 1 0 0 1 1 0 1 1 0 0 0
1 1 1 0 1 1 0 0 0 0 1 1
Ответ: как видно из таблицы, значения правой и левой части равенства совпадают, значит, функции в данной формуле эквивалентны.

2. Используя основные законы и соотношения алгебры логики, необходимо установить справедливость следующей формулы.
.
Решение.
Преобразуем левую часть.

Преобразуем правую часть.
.
Ответ: соотношение в данной формуле не справедливо.

3. Определить к каким классам (константы нуля, константы единицы, самодвойственных функций, монотонных функций, линейных функций, симметрических функций) относится функция следующего вида.
.
Решение.
Составим таблицу истинности.







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

4. Необходимо для данной ФАЛ f(x1, x2, x3, x4) найти ее ДСНФ, КСНФ, ПСНФ, ЭСНФ, ИСНФ, принимающей значение 1 на следующих наборах.
0, 1, 4, 5, 7, 9.
Решение.
Составим таблицу истинности.