Тотожними є ті логічні функції, які мають однакові СДНФ, тобто однакові таблиці істинності. Тому при визначенні тотожності для логічних функцій повинні бути побудовані таблиці істинності або отримані СДНФ. Таблиці або СДНФ порівнюються, і робиться висновок про тотожність функцій.
Тотожно істинними (тавталогіямі) називаються логічні формули, які істинні на всіх наборах змінних. Тотожно хибними (протиріччями) називаються логічні формули, які є неправдивими на всіх наборах змінних.
Приклад 7. Перевірити тотожність логічних функцій:
А. Спрощення функції F.
Застосовуємо закон заперечення і перемножуємо дужки, тобто .
У другій скобці кон'юнкції і склеюються, тому отримуємо:
Мінлива поглинає кон'юнкцію. що дає:
Функція F виявилася записаною в СДНФ, так як містить кон'юнкції однакового рангу, і в них входять всі змінні, від яких вона залежить.
Б. Перетворення функції f.
. Функція f також записана в СДНФ.
Так як СДНФ функцій F і f не збігаються, то вони не є тотожними.
В. Перетворення функції P.
. Отримано СДНФ функції P.
Функції F і P є тотожними, оскільки мають однакові СДНФ.
Приклад 8. Перевірити тотожність логічних функцій F і f.
приймає одиничні значення на наборах 2, 3.
А. Спрощення функції F.
Застосовується закон заперечення:.
У другій скобці змінна поглинає кон'юнкцію. що призводить до наступного результату:.
У другій скобці використовується правило згортки, і потім дужки перемножуються:
Б. Отримання СДНФ функції F.
В. Отримання СДНФ функції f.
Так як функції f приймає одиничні значення на наборах 2 і 3, то її СДНФ матиме вигляд.
Функції F і f мають однакові СДНФ, отже, вони тотожні.
Приклад 9. Перевірити тотожність логічних функцій:
Функція f має наступну мінімальну форму:.
А. Спрощення функції F:
- виняток зайвої кон'юнкції з групи;
- виняток зайвої кон'юнкції yz з групи.
В результаті отримуємо:.
Спрощена форма функції F і мінімальна форма функції f не збігаються. Однак це не означає, що функції не тотожні. Для остаточного висновку потрібно отримати СДНФ обох функцій.
Б. Отримання СДНФ функції F.
Після видалення повторюваних кон'юнкція отримуємо:
В. Отримання СДНФ функції f.
Функції F і f мають однакові СДНФ і приймають одиничні значення на одних і тих же наборах 0, 1, 2, 3, 4, 5, 6, 7. Ці функції тотожні. Так як мінімальні форми функцій не збігаються, то можна зробити висновок, що для функції F була отримана тупикова форма.
Приклад 10. Три безлічі A =, B =, C = задані перерахуванням елементів. Визначити безліч D, що є рішенням D = (A B) C.
Побудуємо безліч D = (A B) C. Виконаємо операції по кроках.
А. A B = =, тому що немає загальних елементів.
Б Б. (A B) C = =. т. к. немає загальних елементів.
Приклад 11 .. Вкажіть, при яких значеннях x, y, p істинно такий вираз:
(P і (x-1
А. Проставимо порядок дій і будемо послідовно визначати значення кожного логічного виразу.
(P і (x-1
Б. Складемо таблицю істинності для кожного варіанту відповіді.