Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Функция , у которой аргументы пробегают множество {0,1} и которая принимает значение из того же множества {0,1}, называется функцией алгебры логики или булевой функцией.
Особое значение имеют так называемые элементарные булевы функции. Двухместными элементарными булевыми функциями являются конъюнкция, дизъюнкция, импликация, сумма по модулю 2, эквиваленция, штрих Шеффера и стрелка Пирса. Символы А и B из табл. 4.2 следует в этом случае толковать как булевы переменные {0,1}.
Имеются две одноместные булевы функции, зависящие от x: тождественная функция и отрицание . Это элементарные функции (табл. 4.3).
Таблица 4.3
x | ||
Имеются две нуль-местные элементарные булевы функции: это константы 0 и 1. Каждой пропозициональной формуле можно сопоставить булеву функцию. Булева функция , сопоставленная пропозициональной формуле A, называется функцией истинности формулы A. Любую такую функцию можно описать с помощью соответствующей таблицы истинности (примеры – табл. 4.3, табл. 4.4, табл. 4.5).
Пусть и – функции истинности формул P и Q; пусть { } – множество тех переменных, которые встречаются хотя бы в одной из функций и . Пропозициональные формулы P и Q называются эквивалентными, если на всяком наборе () значений переменных значения функций и совпадают (эквивалентность обозначают как: P Q).
Пример 4.3. Покажем эквивалентность выражений
P A B и Q A B.
Для этого построим таблицу истинности (табл. 4.4).
Таблица 4.4
A | B | (A, B) P A B | (A, B) Q A B |
Поскольку (A, B) = (A, B), то P Q.
Пример 4.4. Покажем эквивалентность выражений
P A (B C) и Q (A B) (A C).
Для этого снова построим таблицу истинности (табл. 4.5).
Таблица 4.5
A | B | C | (A, B, C) P A (B C) | (A, B, C) Q (A B) (A C) |
Поскольку (A, B, C) = (A, B, C), то P Q. Как можно видеть, в примере 4.3 используются двухместные функции истинности, а в примере 4.4 – трехместные.
Основные эквивалентности:
A A – правило снятия двойного отрицания;
A A A – идемпотентность конъюнкции;
A A A– идемпотентность дизъюнкции;
A*B B*A – коммутативность связки * (символ * является общим
обозначением для связок: , , );
(A*B)*C A*(B*C) – ассоциативность связки *;
A (B C) (A B) (A C) – дистрибутивность («distributivus» – распределительный) конъюнкции относительно дизъюнкции;
A (B C) (A B) (A C) – дистрибутивность дизъюнкции относительно конъюнкции;
(A B) A B и (A B) A B – законы де Моргана;
A (A B) A и A (A B) A – законы поглощения;
A ( A B) A B и A ( A B) A B;
A B A B;
(A B) (A B) ( A B);
A A False – закон противоречия;
A A True – закон исключенного третьего;
A True A;
A True True;
A False False;
A False A;
Дата публикования: 2014-11-03; Прочитано: 1006 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!