Дискр мат лекция 2

1.Алгебра логики

1.1.Высказывания, предикаты и действия над ними

1.1.1.Основные определения

Высказыванием называется предложение, относительно которого можно однозначно сказать, истинно оно или ложно. Например, высказываниями являются: 1) Все студенты данной группы сдали экзамен; 2) 0<1; 3) 5 – четное число.

Вопросительные, восклицательные предложения, определения не являются высказываниями. Например, «Если целое число делится на 2, то оно четное» – не высказывание.

«Если целое число четное, то оно делится на 2» – высказывание. Переменные, которые употребляются для обозначения

высказываний, называются пропозициональными. Значениями пропозициональных переменных являются логические константы «истина» – «и» и «ложь» –«л». В дальнейшем истина будет обозначаться 1, а ложь 0.

Рассмотрим предложение x y 3, где x, y – целые числа. Это

предложение не является высказыванием, т.к. относительно него нельзя сказать, истинно оно или ложно. Однако если заменить x, y

допустимыми значениями, то получится высказывание (1+2=3 – и,

1+4=3 – л).

Предикатом называется предложение с переменными, которое становится высказыванием, если свободные переменные заменить их допустимыми значениями. Например, x y 3 – предикат. По числу

переменных, входящих в предикат, различают одноместные, двуместные и т.д. предикаты. Обозначают предикаты большими

буквами латинского алфавита. При задании предиката			нужно
указывать область допустимых значений переменных.
Элементарным	называется	высказывание,	которое

рассматривается как целое, неразложимое на части. Из элементарных высказываний с помощью логических операций можно получать более сложные высказывания. Значения сложных высказываний задаются с помощью таблиц истинности.

1.1.2. Логические операции над высказываниями Отрицанием высказывания a называется новое высказывание,

истинное только тогда, когда a ложно; обозначается a или a ;

читается: не a , неверно, что a . Например, a – идет дождь, a – нет дождя. Таблица истинности для этой операции имеет вид

a a

01

10

Конъюнкцией a и b называется новое высказывание, истинное только тогда, когда a и b истинны. Конъюнкция a и b называется логическим умножением и обозначается a b , a b , a & b ; читается a и b .

Таблица истинности

	a	b	a b
	0	0	0
	0	1	0
	1	0	0
	1	1	1
Из таблицы видно, что a b		min{a,b}. Если хотя бы одно из двух

высказываний ложно, то их конъюнкция – ложное высказывание. Например, 3 8 5 2 – ложное высказывание.

Дизъюнкцией a и b называется новое высказывание, истинное только тогда, когда хотя бы одно из высказываний a или b истинно. Дизъюнкция a и b иначе называется логическим сложением, обозначается: a b ; читается a или b (союз или в неразделительном смысле: или a , или b или оба вместе).

Таблица истинности

a	b	a b
0	0	0
0	1	1
1	0	1
1	1	1

Из таблицы видно, что a b max{a,b}. Например, 3 8 5 2 –- истинное высказывание.

Импликацией с посылкой a и заключением b называется высказывание, ложное в том и только том случае, когда a истинно, а

b ложно. Импликация иначе называется логическим следованием; обозначается: a b , читается: если a , то b ; из a следует b .

Таблица истинности

a	b	a	b
0	0		1
0	1		1
1	0		0
1	1		1

Между посылкой и заключением могут отсутствовать причинноследственные связи. Это не может повлиять на истинность или ложность импликации. Если посылка ложна, то импликация истинна.

Например, высказывание «если 2	2	5 , то 6 3 9 » – истинно, а
высказывание «если 6 3 9 , то 2	2	5 » – ложно.

Эквиваленцией a и b называется новое высказывание, истинное только тогда, когда a и b имеют одно и то же истинностное значение;

обозначается: a	b , a		b , a b ; читается: a эквивалентно b , a
необходимо и достаточно для b ;					a тогда и только тогда, когда b .
		Таблица истинности
		a		b	a	b
		0		0		1
		0		1		0
		1		0		0
		1		1		1

				1.1.3. Свойства логических операций.
1.	a	a	a,		a	a	a	– идемпотентные законы;
2.	a	b	b	a,	a	b	b	a – коммутативные законы;
	(a		b)	c	a	(b	c)
3.	(a		b)	c	a	(b	c) -ассоциативные законы:
	a (b c)				(a b) (a c)
4.	a	(b		c)	(a	b)	(a	c) – дистрибутивные законы:

5.

0

a

a

1

a

a

0

1 – особая роль 0 и 1.

1

a

1

0

a

0

1

0

6.

(a) a

a –- закон двойного отрицания;

7.

a

b

a

b –- законы двойственности (теоремы де Моргана);

a

b

a

b

8.

a

(a

b)

a

– законы поглощения ;

a

(a

b)

a

9.

a

a

0 – закон противоречия;

10. a

a

1 – закон исключенного третьего

11. a

b

b

a – закон контрапозиции

Все эти соотношения проверяются стандартным способом: путем вычисления обеих частей равенств на всех наборах значений переменных. Например, проверим справедливость закона де Моргана

a b a b .

Таблица 1.1

	a	b	a	b
					a b			a			b			a b
	0	0	0		1			1			1			1
	0	1	1		0			1			0			0
	1	0	1		0			0			1			0
	1	1	1		0			0			0			0

Здесь выделены два столбца, которые нужно сравнить. Эти столбцы

равны. Следовательно, справедливо равенство a b a b .

1.1.4. Формулы логики высказываний Формулами логики высказываний являются

1)элементарные высказывания;

2)высказывания, полученные из элементарных с помощью знаков логических операций.

Знаки логических операций упорядочиваются по старшинству в

следующем порядке	, , , , .	В этом списке знак	имеет
самую большую область действия,		знак – самую маленькую. Во

Например, наоборот.

всякой формуле будем опускать те пары скобок, которые можно восстановить, учитывая порядок старшинства операций. При восстановлении скобок сначала расставляют все скобки, относящиеся

ко всем вхождениям знака , затем	и т.д.
Тождественно истинной или	тавтологией называется

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

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

A A . Если A - противоречие, то A -тавтология и

Формула B называется логическим следствием формул A1 , A2 ,...Am , если при любом выборе значений переменных,

входящих в формулы A1 , A2 ,...Am , B формула B получает значение

истина, если	A1 , A2 ,...Am имеют значения истина. Обозначение:
A1 , A2 ,...Am	B .
Формулы	A и B называются равносильными (эквивалентными),

если при любом выборе значений пропозициональных переменных,

входящих в		A и B , формулы A	и	B принимают одинаковые
истинностные значения. Обозначение: A				B или A	B .
A	B тогда и только тогда, когда A			B и B	A .
	Пример 1.1. Пусть высказывание		x	означает «идет дождь», а
высказывание		y означает «дует ветер». Записать в символической

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

1)Если идет дождь, то дует ветер.

2)Если дует ветер, то идет дождь.

3)Ветер дует тогда и только тогда, когда идет дождь.

4)Если дует ветер, то дождя нет.

5)Неверно, что ветер дует тогда и только тогда, когда нет дождя.

Всимволической форме приведенные высказывания имеют вид:

1) x	y , 2) y	x , 3) x	y , 4) y	x , 5) ( y		x) .

В таблице 1.2 приведены таблицы истинности для каждого из высказываний.

Таблица 1.2

	x	y	x	y	y	x	x	y
									y	x		y	x
															( y		x)
	0	0	1		1		1		1			0			1
	0	1	1		0		0		1			1			0
	1	0	0		1		0		1			1			0
	1	1	1		1		1		0			0			1

Подобным образом можно построить таблицу истинности для любого составного высказывания.

Ряд логических задач сводится к решению обратной задачи: по заданной таблице истинности требуется найти высказывание с этой таблицей истинности. Эта задача всегда имеет решение. Таких

решений может быть несколько,	причем всегда существует решение,
которое содержит только связки	, , .

Рассмотрим случай трех переменных x, y, z . Таблица истинности

в этом случае имеет восемь строк. Если последний столбец таблицы состоит только из нулей, то ему можно сопоставить высказывание

x x или y y или z z , каждое из которых описывается нулевым

столбцом в таблице истинности. Рассмотрим теперь таблицы истинности, которые содержат в последнем столбце хотя бы одну единицу. Вначале построим высказывания, истинные только в одном случае. Такие высказывания приведены в таблице 1.3. Они называются основными конъюнкциями.

Таблица 1.3

x y z Основные конъюнкции

	0	0	0
				x		y		z
	0	0	1
				x		y		z
	0	1	0
				x		y		z
	0	1	1
				x		y		z
	1	0	0
				x		y		z
	1	0	1
				x		y		z
	1	1	0
				x		y		z
	1	1	1	x		y		z

Для того чтобы записать высказывание, соответствующее заданной таблице истинности, нужно образовать дизъюнкцию основных конъюнкций из тех строк таблицы 1.3, которым в заданной таблице истинности соответствует значение 1, т.е. истина.

Пример 1.2. Найти высказывание, имеющее таблицу истинности, представленную таблицей 1.4.

Таблица 1.4.

	x		y		z
	0		0		0		1
	0		0		1		0
	0		1		0		0
	0		1		1		0
	1		0		0		1
	1		0		1		0
	1		1		0		1
	1		1		1		0
Искомое высказывание		имеет				вид x y z x y z x y z .

Здесь знак логического умножения обозначен точкой.

1.2.Булевы алгебры

1.2.1.Аксиомы булевой алгебры

Алгеброй

называется

упорядоченная

пара < B,

>, где

B

–

непустое

множество,

-

множество

операций,

заданных

на

множестве

B .

Иногда

в этот перечень включают выделенные

элементы a1 , a2 ,...,as

алгебры

и

записывают

алгебру в

виде

< B,

, a1 , a2 ,..., as >.

Пусть на множестве B определены 3

операции: две бинарные

(

,

) и одна унарная ( ),

выделены два элемента 0, 1, а также

определено бинарное отношение

между элементами. При этом для

любых x, y, z

B выполняются следующие аксиомы

1. x

x

x,

x

x

x

–

идемпотентные законы;

2.

x

y

y

x,

x

y

y

x – коммутативные законы;

3. (x y) z x (y

z),

(x

y) z

x

(y z)

–

ассоциативные

законы;

4.

x

( y

z)

x

y

x

z

z) – дистрибутивные законы:

x

y

z

(x

y)

(x

5.

0

x

x

,

1 x

x

,

0

1

– тождества с константами 0 и 1.

1

x

1

0 x

0

1

0

6.

(x) x

x –

закон двойного отрицания;

7.

x

y

x

y – законы двойственности (теоремы де Моргана);

x

y

x

y

8.

x

x

1 – закон исключенного третьего

9.

x

x 0 – закон противоречия

Следствия из аксиом

х

х y

x

10.

x

(x

y)

x – законы поглощения (абсорбция):

11.

x

y

x

y

x

– операции склеивания;:

(x

y)

(x

y)

x

12.

x

y

x

z

y z

x

y

x

z

x

x

y

x

y –

(x y) (x z) ( y z)

(x y) (x z)

x (x y)

x y

операции обобщенного склеивания.

Тогда

упорядоченная

пара

B;

,

где

{

, ,

,0,1} ,

называется булевой

алгеброй,

система

B;

;

называется

булевой алгебраической системой.

В отличие от обычной алгебры чисел (например, вещественных) в

булевой алгебре нет операций деления и извлечения корня. Булева алгебра - алгебра без степеней и коэффициентов, так как в силу

x

x

x

x

x

x

x

законов

идемпотентности

x

x

x

.,

x x

x

x

,

x

x

x

...

x

x

x

x

x

...

x

x

Бинарное отношение

обладает следующими свойствами:

для любых x, y, z

B

1)

x

x - рефлексивность;

2)

x

y

y

z

x

z - транзитивность;

3) x y y x x y - антисимметричность

Для любых значений булевых переменных x 1, 0 x .

1.2.2.Примеры булевых алгебр

1)Булеву алгебру образует алгебра высказываний, если

определить						следующие операции										-		дизъюнкция,		&	-
конъюнкция, - отрицание и отношение																		между элементами есть
отношение следствия.
	2) Булеву алгебру образует алгебра множеств. Пусть																		A - конечное
множество,						B – множество всех подмножеств множества													A , B	2 A ,
На множестве B заданы операции																	– объединение множеств,
				– пересечение множеств, – дополнение к множеству,																0	,
1 A, при этом дополнение множества определяется как С=A\C.
Кроме того,						на множестве						B		определена				операция включения .
Тогда			B образует						булеву алгебру относительно операций											,	, .
Такая алгебра называется алгеброй Кантора.
	3). Булеву алгебру образует система чисел {0,1} с операциями
{	, ,			}, где сложение и умножение задаются таблицами
		+		0		1
															0	1
		0		0		1
														0	0	0
		1		1		1
														1	0	1
Если			положить 0						1, 1			0		и	определить операцию				включения
0	0 ,			0		1, 1			1, то получится булева алгебраическая система.
	{0,1};			, ,		,			.

4) Важную модель алгебры Буля дают релейно-контактные схемы. Рассмотрим электрическую цепь, разорванную рядом контактных выключателей. Участки цепи, содержащие эти выключатели, будем обозначать прописными буквами А, В, С,… Они будут служить основными элементами алгебраической системы. Одна цепь может содержать несколько контактов А. Две цепи считаются одинаковыми, если при одном и том же состоянии всех контактов обе цепи

одновременно пропускают или одновременно не пропускают ток.

Под суммой А+В двух элементов цепи мы будем понимать цепь, полученную в результате параллельного соединения звеньев. Сумма А+В пропускает ток, если пропускает ток хотя бы один из элементов.

A

A+B

B											AB
					A		B

Под произведением А В будем понимать цепь, полученную в результате последовательного соединения звеньев А и В. Очевидно, что цепь А В пропускает ток лишь в том случае, когда пропускают ток оба звена.

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

	A
	A+AB=A
A	B

A

A(A+B)=A

A

B

Дистрибутивные законы также выполняются. Покажем, что (А+В)Г=АГ+ВГ