Задание 2
Проверить двумя способами, будут ли эквивалентны следующие функции. А) составление таблиц истинности; Б) приведением к СКНФ или СДНФ с помощью эквивалентных преобразований.
,
Задание 3
С помощью эквивалентных преобразований привести формулу ДНФ, КНФ, СДНФ, СКНФ. Построить полином Жегалкина методом неопределенных коэффициентов.
Задание 4
С помощью Карт Карно, построить МДНФ и МКНФ функций: а) f(x,y,z); и в) f(x1,x2,x3,x4) заданных вектором своих значений.
а) (1100 0101); б) (1110 0101 0011 0101).
а) f(x,y,z) (1100 0101)
Занесём данные в карту Карно. Отметим клетки, где функция равна нулю. Функция f равна нулю, на наборах, являющихся двоичным разложением чисел: 2, 3, 4, 6 (т.к. отсчёт начинается с 0). Таким образом f(0,1,0) = f(0,1,1) = = f(1,0,0) = f(1,1,0) = 0
Задание 5.
Используя критерий полноты (теорему Поста) проверить, является ли полной система функций S={f1,f2}. ;
Проверим, какими свойствами обладают данные функции:
1)Сохранимость константы 0:
– сохраняет константу 0.
– не сохраняет константу 0.
2)Сохранимость константы 1:
– не сохраняет константу 1.
– сохраняет константу 1.
3)Самодвойственность:
Составим таблицы истинности для функций: и
Задание 6.
Используя теорему о дедукции и теорему о полноте проверить выводимость формулы ИВ.
├
Используя теорему о дедукции последовательно, заключаем, что
├├├
По теореме о полноте заключаем, что формула доказуема тогда и только тогда, когда φ является тавтологией. Построим таблицу истинности для формулы φ:
A
B
φ
0
0
1
1
0
0
1
0
1
1
0
1
1
1
1
0
0
1
1
1
1
1
1
1
0
1
1
1
Т.к. φ является тавтологией (т.е. равно тождественно 1), то, следовательно, формула A выводится из формулы и .