Математика и информатика часть II. Информатика Пособие для студентов

Скачать 2.97 Mb.

Название	Математика и информатика часть II. Информатика Пособие для студентов
страница	6/27
Тип	Методические указания

rykovodstvo.ru > Руководство эксплуатация > Методические указания

1 2 3 4 5 6 7 8 9 ... 27

Практическое занятие № 3. Алгебра логики. Операции над высказываниями

1. Цель занятия

Цель занятия: ознакомиться с понятием «высказывание». Знать основные логические операции. Уметь выполнять операции над высказываниями, читать и строить таблицу истинности.

Теоретический материал для практического занятия №3

Логика – одна из древнейших наук. Её основателем считается древнегреческий мыслитель Аристотель (384 – 322гг. до н. э.), который первым систематизировал формы и правила мышления, обстоятельно исследовал категории: понятие и суждение, подробно разработал теорию умозаключений и доказательств, описал ряд логических операций, сформулировал основные законы мышления.

Продолжение развития логики связано с математической логикой. Основоположником математической логики считается великий математик и философ Готфрид Вильгельм Лейбниц (1646-1716). Он попытался построить первые логические исчисления: арифметические и буквенно-алгебраические. Но Лейбниц высказал только идею, а развил её окончательно англичанин Джордж Буль (1815-1864). Он вывел для логических построений особую алгебру (алгебру логики). В отличие от обычной логики, в ней символами обозначаются не числа, а высказывания. Алгебра логики (булева алгебра) изучает высказывания, рассматриваемые со стороны их логических значений (истинности или ложности), и логические операции над ними.

Создание алгебры логики представляло собой попытку решать традиционные логические задачи алгебраическими методами. С появлением теории множеств (70-е годы 19 в.) и дальнейшим развитием математической логики (последняя четверть 19 в. и первая половина 20 в.) предмет алгебры логики значительно изменился. Основным предметом алгебры логики стали высказывания.

Высказыванием в математике называют предложение, относительного которого имеет смысл вопрос истинности или ложности его.

В логике считают, что из двух данных предложений можно образовать новые предложения, используя для этого слова: «и, или, если…, то», которые называют логическими связками. Предложения, образованные из других предложений с помощью логических связок, называют составными. Выделяют пять основных логических связок, которые позволяют получить новые высказывания:

1) Отрицание – это высказывание, которое получается из данного высказывания А с помощью слова «не». Отрицание обозначается

. Высказывание А=«студент сдал сессию». Высказывание

=«студент не сдал сессию».

2) Конъюнкция высказываний А и В – это высказывание АB, которое истинно, когда оба высказывания истинны, и высказывание АB ложно, когда хотя бы одно из этих высказываний ложно. Конъюнкция получается из двух данных высказываний А и В с помощью союза «и».

Пример 1.

Высказывание А= «студент сдаёт сессию без троек, двоек». Высказывание В= «студент получает стипендию».

Конъюнкцией высказываний А и В будет высказывание АB=«студент сдаёт сессию без троек, двоек и студент получает стипендию».

3) Дизъюнкция высказываний А или В – это высказывание А B, которое истинно, когда истинно хотя бы одно из этих высказываний, и высказывание А B ложно, когда оба высказывания ложны. Дизъюнкция получается из двух данных высказываний А, В с помощью союза «или».

Пример 2.

Для высказываний А и В примера 1 дизъюнкция имеет вид:

АB=«студент сдаёт сессию без троек, двоек или студент получает стипендию или то и другое».

4) Импликация образуется из двух данных высказываний А и В с помощью слов «если…, то…». Импликация обозначается: АВ (если А, то В).

Пример 3.

Для высказываний А и В примера 1 импликация имеет вид:

АВ = «если студент сдаёт сессию без троек, двоек, то студент получает стипендию».

5) Эквиваленция образуется из двух данных высказываний А и В с помощью слов «тогда и только тогда, когда…».

Эквиваленция обозначается А  В.

Пример 4.

Для высказываний А и В примера 1 эквиваленция имеет вид:

А В= «студент сдаёт сессию без троек, двоек тогда и только тогда, когда студент получает стипендию».

Пример 5.

Эквиваленция из высказываний В и А примера 4 будет:

ВА = «студент получает стипендию тогда и только тогда, когда студент сдаёт сессию без троек, двоек».

В математической логике не рассматривается конкретное содержание высказывания, важно только, истинно оно или ложно. Поэтому высказывания можно представить некоторой переменной величиной, значением которой может быть только «0» или «1». Если высказывание истинно, то его значение равно «1», если ложно, то равно «0».

2.1. Логические операции

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

В таблице 3.1 приведены основные логические операции (связки).

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

Таблица 3.1

№	Операция	Обозначение			операции с высказываниями	Комментарий
№	Операция	Математическая логика	Логика высказываний	Информатика	операции с высказываниями	Комментарий
1	Отрицание	() или	«не»	NOT		унарная операция
2	Конъюнкция	умножение	«и»	AND	AB; (АВ)	бинарная операция
3	Дизъюнкция	сложение	«или»	OR	AB; (А+В)	бинарная операция
4	Импликация		«если …, то …»	IMP	AB	бинарная операция
5	Эквиваленция	; (~)	равнозначно	EQV	AB	бинарная операция
6	Антиконъюнкция	\| (штрих Шеффера)	«и-не»		A \| B	бинарная операция
7	Антидизъюнкция	(стрелка Пирса)	«или-не»		AB	бинарная операция
8	Исключающее «или» (разделительная дизъюнкция)			XOR	АВ	бинарная операция

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

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

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

Таблица 3.2

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

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

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

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

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

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

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

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

Пример 6.

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

P= ((x z) | ((x  y)  (y  z)))(ØyØx)

Решение.

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

Примечание

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

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

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

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

((x  z) | ((x  y) ~ (y  z)))(y + x).

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

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

Таблица 3.4

Вариант	Составить таблицу истинности
Вариант	Задание 1	Задание 2
1	X=(((AB)B)C)(AC)	Z=(B+C)+(D+B)*(C+D)
2	D=((AC)B)(C(AB))	B=X+Z+XY*(Z+Y)
3	W =(XZ)(YZ) (XY)	V=B+DC+B*(C+D)
4	Z=(AB)(B C)  (AC)	C=X+X*(Z+Y)+YZ
5	R=(((ZY)X)Y)(XZ)	D=(X+Z)+(Y+X)+ZY
6	P=(AB) (BC)(AC)	Y=BC+AB+CA
7	A=((YX)Z)  (X(YZ))	G=Z*(Y+X)+ZX+Y
8	B=(((ZY)X)Y)(XZ)	H=C+(D*B) + (C+D)+ B
9	C=(XZ)(YZ) (YX)	K=X+(Z*Y)+Y(Z+X)
10	D=(((AB)B) C)(AC)	S=B+(AB+C)+AC
11	F=(((AC) B)C)(AB)	N=(Z+X)Y+(Z+Y)X
12	G=(((AB)  B)C)(AC)	P=(B+C)A+BC+A
13	M=(((AB)B) C)(AC)	U=X*(Z+Y)+YZ+X
14	P=(((AB)B)C)  (AC)	L=B+(D+B)+(C+D )+C
15	R=(((AB)B) C)(AC)	D=XY+Z+(Y+X)+Z
16	T=(((AB)B)C)(AC)	P=AB+C+A+BC
17	Q=(((AB) B)C)(AC)	D=XZ+X*(Z+Y)+Y
18	S=(((AB)C) B)(AC)	A=B+DB+(C+D)+C
19	V=((AB) C)  (AC) )B	Z=A(B+C)+BC+CA
20	M=(((AB)B)C)(AC)	W=Z+XY+Z(X+Y)
21	G=((AB) B)(AC) (CA)	Z=AB+BC+CA
22	W=(((AB)B) C)(AC)	G=X(Z+Y)+Z(Y+X)
23	X=(((AB)B) C)  (AC)	Q=A+BC+A(B+C)
24	Y=(((AB)B)C)(AC)	R=XZ+Y(X+Z)+Y
25	Z=(((AC)B)C)  (AB)	R=(X+Y)Y+(Z+X)Z
26	W=((AB)  C)(A(BC))	F=(B+C)+D(B+CD)
27	D=(((ZY)  X)Y)  (ZX)	Z=AB(C+B)+CA
28	R=(ACB)(C(AB))	R=X+(Y+YZ)+ZX
29	H=(((ZX) Y)Z)(YX)	D=(A+B)C+AB+C
30	M=((CB)(BA)) (AC)	F=B+C(D+B)+CD

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

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

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

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

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

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

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

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

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

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

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

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

А	0	0	1	1
В	0	1	0	1
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= А?В, которая соответствует таблице истинности.

А	0	0	1	1
В	0	1	0	1
F	1	1	0	1

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

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

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

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

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

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