Формулы и функции алгебры логики

 

Высказывания, образованные из элементарных переменных высказываний путем применения операций алгебры логики, называются сложными высказываниями или формуламиалгебры логики.

Если переменным, входящим в формулу, задать определенные значения из множества , то и формула примет определенное значение из того же самого множества, отсюда, каждая формула алгебры логики определяет некоторую свою функцию, причем и аргументы и сама функция могут принимать лишь два значения 0 или 1.

Функцию , принимающую значения 0 или 1 и определенную на всевозможных n-мерных наборах из 0 и 1, называют логической функциейили функцией алгебры логикиот n переменных.

Любую функцию алгебры логики от n переменных можно представить с помощью таблицы истинности, в которой строки (их всего ) располагаются в порядке возрастания двоичных чисел:

 

		.....
		.....
		.....
...	...	.....	...	.....
		.....

 

Числовсех функций алгебры логики от n переменных равно , функций алгебры логики от двух переменных – 16.

Рассмотрим эти функции:

 

x

y

 

= 0 – «константа 0»;

= x ∙ y – «конъюнкция» (x и y);

= – «левая импликация»;

= x – «переменная x»;

= – «правая импликация»;

= y – «переменная y»;

= = – «сложение по модулю 2»;

= – «дизъюнкция» (x или y);

= = – «стрелка Пирса» (x стрелка y);

= = – «эквивалентноcть» (x эквивалентно y);

= – «отрицание» (не y);

= = – «x правая импликация y, или y импликация x»;

= – «отрицание»(не x);

= x → y = – «импликация» (если x, то y);

= x|y = – «штрих Шеффера» (x штрих y);

=1 – «константа 1».

Для удобства записей выражений в алгебре логике в дальнейшем мы будем придерживаться следующих правил:

· если над некоторым выражением стоит отрицание, то это выражение мы не будем заключать в скобки;

· знак «& » мы будем иногда опускать (как знак операции пересечения в алгебре множеств);

· будем считать, что знак «& » сильнее, чем знаки дизъюнкции, сложения по модулю 2, эквивалентности, импликации, стрелки Пирса и штриха Шеффера, тем самым мы будем, где это возможно, опускать скобки;

· на основании закона ассоциативности мы будем опускать скобки при записи нескольких идущих подряд дизъюнкций и конъюнкций.

Согласно определению таблица истинности логической формулы выражает соответствие между всевозможными наборами значений переменных и значениями формулы.

Для формулы, которая содержит две переменные, таких наборов значений переменных всего четыре: (0, 0), (0, 1), (1, 0), (1, 1).

Если формула содержит три переменные, то наборов значений переменных восемь: (0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1).

Количество наборов для формулы с четырьмя переменными равно шестнадцати.

Удобной формой записи при нахождении значений формулы является таблица, содержащая кроме значений переменных и значений формулы также и значения промежуточных формул.

Если при всех наборах значений переменных x и y формула принимает значение 1, то является тождественно истинной, если при всех наборах значений переменных x и y формула принимает значение 0, то является тождественно ложной, если формула в некоторых случаях принимает значение 1, а в некоторых – 0, то есть является выполнимой.

Булевы функции могут быть заданы либо с помощью таблиц истинности (единственным образом), либо с помощью логических формул (неединственным образом). Если таблицы истинности двух булевых формул совпадают, то эти формулы эквивалентны и определяют одну и ту же булеву функцию.

Пример 1. Проверить эквивалентность булевых формул .

Решение:

Построим таблицу истинности для функции .

 

 

Построим таблицу истинности для функции .

 

 

Результирующие столбцы в таблицах истинности совпадают, следовательно, формулы эквивалентны.

Пример 2. Проверить, будут ли эквивалентны следующие формулы:

xÙ (y ® z) и (x Ù y) ® (x Ù z).

Решение:

 

x	y	z	y ® z	x Ù (y ® z)	x Ù y	x Ù z	(x Ù y) ® (x Ù z)

 

Таблицы истинности не совпадают, следовательно, формулы не эквивалентны.

Пример 3. Проверить, будут ли эквивалентны следующие формулы: и .

Решение:

 

x	y	z

 

Функции не эквивалентны.

Некоторые преобразования логических формул похожи на преобразования формул в обычной алгебре (вынесение общего множителя за скобки, использование переместительного и сочетательного законов), тогда как другие преобразования основаны на свойствах, которыми не обладают операции обычной алгебры (использование распределительного закона для конъюнкции, законов поглощения, склеивания, де Моргана).

Способы, применяемые при упрощении логических формул:

1) Законы алгебры логики применяются в следующей последовательности: правило де Моргана, сочетательный закон, правило операций переменной с ее инверсией и правило операций с константами;

2) Применяется правило де Моргана, выносится за скобки общий множитель, используется правило операций переменной с ее инверсией.

Упражнения

1. Используя основные законы алгебры логики, доказать равносильность:

a) и ;

b) и ;

c) и ;

d) и .

 

Индивидуальное задание

 

5 Проверить эквивалентность булевых формул, используя таблицы истинности:

5.1 ;

5.2

5.3 ;

5.4 ;

5.5 ;

5.6 ;

5.7 ;

5.8 ;

5.9 ;

5.10 ;

5.11 ;

5.12 ;

5.13 ;

5.14 ;

5.15 .

 

 

1234567Следующая ⇒

Поделиться:

Популярное:

1. B. Функции языка как театральной коммуникативной системы
2. I. КРАТКИЕ СВЕДЕНИЯ О СТРОЕНИИ И ФУНКЦИИ МИОКАРДА
3. III. Вегетативные функции НС.
4. Xlabel('Значения x'); ylabel('Значения функции'), grid
5. Анализ структуры и выполняемые функции информационной подсистемы «Кадры» ОГУ
6. Асимптоты графика функции и их отыскание
7. Билет 5 Основные черты, функции и Юридические свойства Конституции
8. Биологические функции пептидов и белков
9. Блок 20. Функции администратора зала и администратора кассы
10. Бухгалтерский учет: его задачи, функции и
11. В том, что любой живой организм состоит из клеток, но клетки выполняют разные функции.
12. Виды, функции и стадии правотворчества