Основные логические операции

 

Таблица 3.1

№	Операция	Обозначение	операции с высказываниями	Комментарий
Математическая логика	Логика высказываний	Информатика
	Отрицание	(Ø) или	«не»	NOT		унарная операция
	Конъюнкция	умножение	«и»	AND	A B; (А×В)	бинарная операция
	Дизъюнкция	сложение	«или»	OR	A B; (А+В)	бинарная операция
	Импликация		«если …, то …»	IMP	A B	бинарная операция
	Эквиваленция	; (~)	равнозначно	EQV	A B	бинарная операция
	Антиконъюнкция	| (штрих Шеффера)	«и-не»		A | B	бинарная операция
	Антидизъюнкция	(стрелка Пирса)	«или-не»		A B	бинарная операция
	Исключающее «или» (разделительная дизъюнкция)	Ä		XOR	АÄВ	бинарная операция

Приоритет связок соответствует номеру в таблице 3.1:

• Отрицание.
• Конъюнкция.
• Дизъюнкция.
• Импликация.
• Эквиваленция.
• Антиконъюнкция.
• Антидизъюнкция.

Таблица истинности для основных бинарных логических операций

Таблица 3.2

№	Высказывания	Наименование операции
Конъюнкция	Дизъюнкция	Импликация	разделительная дизъюнкция	Эквиваленция	Антиконъюнкция	Антидизъюнкция
X	Y						|
AND	OR	IMP	XOR	EQV	«и-не»	«или-не»

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

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

Переменная, значениями которой являются высказывания, называется пропозициональной переменной.

Правила сокращения записей в пропозициональных формулах:

• вместо Ø А пишут ;
• вместо А1 и А2 пишут А1 Ù А2 (А1×А2);
• вместо А1 или А2 пишут А1 Ù А2 (А1+А2);
• внешние скобки опускаются.

3. Примеры выполнения задания к практическому занятию №3

Решение логических задач средствами алгебры логики

Пример 6.

Составить таблицу истинности для данной формулы:

P= ((x Þz) | ((x Ù y) Û (y Ù z)))¯(ØyÚØx)

Решение.

1. Построить таблицу, где первые три столбца относятся к разделу «Дано».
2. Остальные столбцы относятся к разделу «Решение».
3. Посчитать количество операций с учётом их приоритета.
4. В данном задании всего должно быть выполнено 9 операций.
5. Под каждую операцию выделяется в таблице истинности 3.3 столбец с указанием номера с 1÷9.
6. Согласно приоритету в первую очередь выполняются операции в скобках.
7. Так как в последней скобке операции «отрицание», предпочтительно их сразу записать. Поэтому первые три столбца с номерами 1, 2, 3 отражают операции в последней скобке.
8. Затем выполняются операции во внутренних скобках слева направо, которые приведены в столбцах с номерами 4, 5, 6.
9. В столбце 7 выполняется операция во вложенных скобках.
10. В столбце 8 выполняется операция во внешних скобках.
11. В столбце 9 выполняется операция «¯» антидизъюнкция.

В таблице истинности 3.3 приводится решение примера 6.

Таблица 3.3

x	y	z	`x	`y	`yÚ`x	x Þ z	x Ùy	y Ùz	(x Ù y)Û(yÙ z)	(xÞz) | ((xÙ y)Û (yÙz))	P
Входные данные (дано)	номер логической операции с учётом приоритета

Примечание

1. Каждую операцию следует включить в таблицу истинности вида 3.3.

2. Нельзя в одном столбце выполнять более одной операции.

3. При выполнении задания следует учесть последовательность выполнения действий с учётом их приоритета, согласно которому в первую очередь выполняются операции в скобках. Из логических операций вначале выполняется отрицание, затем конъюнкция и т.д., как указано в таблице 3.1. В таблице 3.3 последовательность выполнения действий отражается в третьей строке номером логической операции с учётом приоритета.

4. Формула в задании может быть записана с учётом сокращений в виде:

((x ® z) | ((x × y) ~ (y × z)))¯(Øy + Øx).

Задания к практическому занятию № 3

• В таблице 3.4 выбрать свой номер варианта;
• По примеру 6 выполнить задания для практического занятия № 3, учитывая, что в каждом столбце таблицы может быть представлена только одна логическая операция;
• Оформить выполнение работы в виде таблицы 3.3.
• Представить преподавателю выполненную работу и защитить её.

Таблица 3.4

Вариант	Составить таблицу истинности
Задание 1	Задание 2
	X=(((AÙB)Ú`B)¯C)Þ(A½C)	Z=(`B+C)+(`D+B)*(`C+D)
	D=((`AÙC)ÞB)½(`CÛ(AÚB))	B=X+Z+`XY*(`Z+`Y)
	W =(XÞZ)Ú(YÙZ) ¯(`XÛY)	V=`B+`DC+B*(`C+D)
	Z=(AÙB)Ú(`B ÞC) Û (`A½C)	C=`X+X*(`Z+`Y)+YZ
	R=(((ZÙY)Ú`X)¯Y)½(XÞ`Z)	D=(X+Z)+(`Y+`X)+`ZY
	P=(AÛB)Ú (B¯`C)Þ(AÙC)	Y=`BC+`AB+`CA
	A=((YÚX)Û`Z) Ù (XÞ(Y½Z))	G=Z*(Y+`X)+`ZX+`Y
	B=(((ZÙY)Ú`X)ÛY)Þ(X½Z)	H=C+(`D*B) + (`C+D)+ `B
	C=(XÞZ)Ú(Y½Z)Ù (`YÛX)	K=`X+(`Z*`Y)+Y(Z+X)
	D=(((AÙB)Ú`B) ¯`C)Þ(AÛC)	S=`B+(`AB+`C)+AC
	F=(((AÛC) ¯`B)ÚC)Þ(AÙB)	N=(Z+`X)Y+(`Z+`Y)X
	G=(((AÙB) Û B)¯C)Þ(AÚ`C)	P=(`B+C)*`A+B*`C+A
	M=(((AÙB)Ú`B) Û`C)Þ(A½C)	U=`X*(`Z+`Y)+YZ+X
	P=(((AÙB)Ú`B)½C) Û (AÞ`C)	L=`B+(`D+B)+(`C+D)+C
	R=(((AÙB)Ú`B) ¯C)Þ(`AÛC)	D=`XY+`Z+(`Y+X)+Z
	T=(((AÛB)Ù`B)½C)Þ(AÚC)	P=A*`B+C+`A+B*`C
	Q=(((AÙB) Û`B)¯C)Þ(A½C)	D=`XZ+X*(`Z+`Y)+Y
	S=(((AÙB)ÚC) Û`B)Þ(`A½C)	A=`B+`DB+(C+D)+`C
	V=((AÙB) ÞC) Û (A½C))Ú`B	Z=`A(B+C)+`BC+`CA
	M=(((AÙB)Ú`B)¯C)Þ(AÛC)	W=`Z+XY+Z(`X+`Y)
	G=((A½B) Û`B)Þ(AÙC) ¯(`CÚ`A)	Z=`AB+`BC+`CA
	W=(((AÙB)½`B) ÛC)Þ(AÚ`C)	G=`X(Z+Y)+`Z(`Y+X)
	X=(((AÙB)Ú`B) ½C) Û (`A½C)	Q=A+`BC+`A(B+`C)
	Y=(((AÙB)Ú`B)¯C)½(AÛ`C)	R=XZ+Y(`X+`Z)+`Y
	Z=(((AÛC)Ú`B)½C) Þ (`AÙB)	R=(`X+Y)*`Y+(Z+X)*`Z
	W=((AÙB) Û `C)¯(`AÚ(BÞC))	F=(`B+C)+`D(B+`CD)
	D=(((Z½Y) Þ X)Ú`Y) Ù (`ZÛX)	Z=`AB(C+`B)+`CA
	R=(AÙCÚ`B)Þ(C½(`A¯B))	R=`X+(Y+`YZ)+`ZX
	H=(((ZÙX) Û`Y)¯Z)Þ(Y½X)	D=(A+`B)C+`AB+`C
	M=((`CÞB)½(BÙA))Ú (`AÛC)	F=`B+C(`D+B)+`CD

Задание ИДЗ №3 по теме «Алгебра логики» в Приложении №1 (Задание 3).

Вопросы для самоконтроля к практическому занятию № 3. Тема «Алгебра логики»

1. Логическая операция АÙВ – это:

1) импликация; 2) конъюнкция; 3) дизъюнкция 4) эквиваленция.

2. Логическая операция АÚВ – это:

1) импликация; 2) конъюнкция; 3) дизъюнкция 4) эквиваленция.

3. Логическая операция АÞВ – это:

1) импликация; 2) конъюнкция; 3) дизъюнкция 4) эквиваленция.

4. Логическая операция АÛВ – это

1) импликация; 2) конъюнкция; 3) дизъюнкция 4) эквиваленция.

5. С помощью таблицы истинности получается результат логической функции F=А Þ B

Выбрать строку, которая соответствует результату логической функции в таблице.

А
В
F	?	?	?	?

1) 0 1 1 1;

2) 0 0 0 1;

3) 0 1 1 0;

4) 1 1 0 1.

6. Пусть через А обозначим высказывание «студент знает математику», через В обозначим высказывание «студент любит спорт». Выбрать конъюнкцию, дизъюнкцию, импликацию, эквиваленцию этих высказываний.

1) «Если студент знает математику, то студент любит спорт»;

2) «студент знает математику или студент любит спорт»;

3) «студент знает математику и студент любит спорт»;

4) «студент знает математику тогда и только тогда, когда студент любит спорт».

7. Логическая операция эквиваленция обозначается знаком:

1) Ú; 2) Ù; 3) Û; 4) Þ.

8. Выбрать логическую операцию F= А?В, которая соответствует таблице истинности.

А
В
F

1) конъюнкция; 2) эквиваленция; 3) дизъюнкции; 4) импликация.

9. Пусть через А обозначим высказывание «Ада Лавлейс-первый в мире программист», через В обозначим высказывание «Джон фон Нейман - автор классического компьютера». Выбрать конъюнкцию, дизъюнкцию, импликацию, эквиваленцию этих высказываний.

1) «Если Ада Лавлейс-первый в мире программист, то Джон фон Нейман автор классического компьютера»;

2) «Ада Лавлейс-первый в мире программист или Джон фон Нейман автор классического компьютера»;

3) «Ада Лавлейс-первый в мире программист в мире и Джон фон Нейман автор классического компьютера»;

4) «Ада Лавлейс-первый в мире программист в мире тогда и только тогда, когда Джон фон Нейман автор классического компьютера».