Многочлен Жегалкина. Таблица истинности. Эквивалентность формул

  • Просмотров 2879
  • Скачиваний 441
  • Размер файла 45
    Кб

Untitled Построить таблицы соответствующих функций и выяснить, эквивалентны ли формулы а) Составим таблицу истинности для функции U: x y z отрицание x отрицание у дизъюк ция конъюнк ция имплика ция импликация ( импликация 0 0 0 1 1 1 0 1 1 1 0 0 1 1 1 1 1 1 1 1 0 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1 1 1 1 1 1 0 0 0 1 1 0 0 1 1 1 0 1 0 1 1 1 0 1 1 1 1 0 0 0 0 0 1 0 1 1 1 1 0 0 0 0 1 0 1 Мы получили формулу U(11111111). Составим таблицу истинности для функции V: x y z импликация отрицание у отрицание x импликация 0 0 0 1 1 1 1

1 0 0 1 1 1 1 1 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 0 1 1 1 0 1 0 0 1 1 1 1 1 1 0 0 1 1 Мы получили формулу V(11111111) Сравнивая таблицы функций U и V, видим, что U = V. Значит, формулы U и V эквивалентны. б) Составим таблицу истинности для функции U: x y z отрицание x отрицание у конъюнкция отрица ние z конъюнк ция имплика ция импликация импликация 0 0 0 1 1 1 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 0 1 0 1 0 0 1 1 1 0 1 0 1 1 1 0 0 0 0 1 0 1 1 0 0 0 1 0 1 0 1 0 1 1 0 1 0 1 0 0 0 1 0 1 1 1 0 0 0 0 1 0 1 0 1 1 1 1 0 0 0 0 0 1 0 1 импликация 1 1 0 0 1 1 1 1 Мы

получили формулу U(11001111). Составим таблицу истинности для функции V: x y z отрицание z импликация конъюнкция отрицание конъюнкции 0 0 0 1 1 0 1 0 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 1 0 0 0 1 1 0 0 1 1 1 0 1 0 1 0 1 1 0 1 1 0 1 1 1 0 1 1 1 0 0 0 1 Мы получили формулу V(11110001) Сравнивая таблицы функций U и V, видим, что U ≠ V. Значит, формулы U и V неэквивалентны. в) Составим таблицу истинности для функции U: x y z отрицание z эквивалентность импликация отрицание импликации Сумма по модулю 2

дизъюнкция 0 0 0 1 1 1 1 0 1 1 0 0 1 0 1 1 1 0 0 0 0 1 0 1 0 1 1 0 1 1 0 1 1 0 0 1 1 0 0 0 1 0 0 1 0 1 1 0 0 0 1 0 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 0 0 0 1 1 1 0 1 0 0 1 1 1 Мы получили формулу U(10100101). Составим таблицу истинности для функции V: x y z импликация эквивалентность 0 0 0 1 0 0 0 1 0 1 0 1 0 1 0 0 1 1 1 0 1 0 0 1 1 1 0 1 0 0 1 1 0 1 1 1 1 1 1 1 Мы получили формулу V(01001011) Сравнивая таблицы функций U и V, видим, что U ≠ V. Значит, формулы U и V неэквивалентны. Методом неопределенных коэффициентов построить полином Жегалкина для

следующих функций. а) Сначала составим таблицу истинности для функции x y z отрицание x отрицание у конъюнкция дизъюнкция 0 0 0 1 1 1 1 0 0 1 1 1 1 1 0 1 0 1 0 0 0 0 1 1 1 0 0 1 1 0 0 0 1 0 0 1 0 1 0 1 0 1 1 1 0 0 0 0 0 1 1 1 0 0 0 1 Полином Жегалкина для нее представляется в виде: Последовательно подставляя значения переменных из таблицы, получаем: Следовательно функция б) Сначала составим таблицу истинности для функции x y z конъюнкция импликация 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 1 1 0 1 1 0 0 0 1 1 0 1