Главная   Онлайн инструменты по математической логике   Мат. логика теория   Как считает компьютер?   Схемы для ЭВМ    

Эквивалентные функции

Определение булевой функции
Элементарные булевы функции
Задание булевых функций посредством элементарных
Существенные и несущественные переменные
Эквивалентные функции
Основные эквивалентности
Функциональная полнота
Нормальные формы
Совершенные нормальные формы
Минимизация ДНФ методом Квайна
Карты Карно
Полином Жегалкина
Высказывания
Предикаты
Кванторы
Определение формальной теории
Исчисление высказываний
Теорема о дедукции. Полнота ИВ
Автоматическое доказательство теорем
Метод резолюций в ИВ
Определение алгоритма
Машина Тьюринга
Рекурсивные функции
Алгоритмически неразрешимые задачи
Алгоритмы и их сложности




     Зная таблицу истинности для элементарных функций, можно вычислить таблицу истинности той функции, которую реализует данная формула.
     Пример 1: F1=X1•X2v(X1•¬X2v¬X1•X2)

X1X2X1•¬X2¬X1•X2X1•¬X2v¬X1•X2X1•X2F1
0000000
0101101
1010101
1100011

     Таким образом, формула F1 реализует дизъюнкцию.
     Пример 2: F2=X1•X2→X1

X1X2X1•X2F2
0001
0101
1001
1111

     Таким образом, формула F2 реализует константу 1.
     Пример 3: F3=((X1•X2)⊕X1)⊕X2

X1X2X1•X2(X1•X2)⊕X1F3
00000
01001
10011
11101

     Таким образом, формула F3 реализует дизъюнкцию.
     Булевы функции F1 и F2 называются эквивалентными, если на всяком наборе (a1, a2 ... an) нулей и единиц значения функций совпадают. Обозначение эквивалентных функций следующее: F1=F2.
     Согласно приведенным примерам 1-3, можно написать:
     •   X1•X2v(X1•¬X2v¬X1•X2)=X1vX2
     •   X1•X2→X1=1
     •   ((X1•X2)⊕X1)⊕X2=X1vX2

@ 2010 - 2017 tablica-istinnosti.ru Рейтинг@Mail.ru