Математическая логика и теория алгоритмов

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

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

Пример 3. Определить к каким классам (константы нуля, константы единицы, самодвойственных функций, монотонных функций, линейных функций, симметрических функций) относится функция.

Пример 4. Используя метод неопределенных коэффициентов, необходимо найти МДНФ функции.

Всего 10 практических задач.

Пример 1.

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

f(x_1,x_2,x_3)=((x_1 ) ?x_2?x_3 )>[(((x_2 ) ??x_1 ) ?)v(x_3 ) ? ]=[(x_1?(x_2 ) ? )|(x_3 ) ? ]>[(((x_2 ) ?vx_1 ) ?>(x_2v(x_1 ) ?)) ? ]

Решение:

Построение таблицы истинности

Пример 2.

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

[(x_1?x_2)>x_3 ]v(x_1 x_2 x_3?1)=(x_1>(x_2 |x_3)) ?

Пример 3.

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

f(x_1,x_2,x_3 )=(x_1 ) ? (x_2 ) ??x_3?(x_3 ) ? x_1

Пример 4.

Необходимо для данной ФАЛ f(x_1,x_2,x_3,x_4 ) найти ее ДСНФ, КСНФ, ПСНФ, ЭСНФ, ИСНФ принимающей значение 1 на следующих наборах: 2,7,8,9,10,11

Пример 5.

Используя метод неопределенных коэффициентов, необходимо найти МДНФ функции f(x_1,x_2,x_3 ) принимающей значение 1 на наборах: 1,2,5,7

Пример 6

Используя метод Квайна, необходимо найти МДНФ функции f(x_1,x_2,x_3,x_4 ) принимающей значение 1 на наборах: 0,3,7,8,9,13,14,15

Пример 7

Используя метод Квайна – Мак-Класки, необходимо найти МДНФ функции F(x_3,x_2,x_1,x_0 ) принимающей значения 1 на наборах: 2, 3, 4, 5, 10, 13, 14

Пример 8.

Используя метод диаграмм Вейча, необходимо найти МДНФ функции F(x_3,x_2,x_1,x_0 ) принимающей значения 1 на наборах: 0, 4, 5, 6, 7, 134, 15

Пример 9.

Доопределить функцию f(x_1,x_2,x_3,x_4 )=0,3,7,8,11,13*,14,15*

Пример 10.

Найти производную третьего порядка f(x_1,x_2,x_3 )=(x_1 ) ? (x_2 ) ??x_3