A®B; B®C; C 1 страница. Команда – победитель турнира станет обладателем переходящего Большого Кубка.

Команда – победитель турнира станет обладателем переходящего Большого Кубка.

Команды, занявшие призовые места, награждаются памятными призами и подарками.

Результаты турнира будут опубликованы на сайте Туристского клуба МИЭМ НИУ ВШЭ http://tkmiem.ru/ leon2015 и в группе http://vk.com/tkmiem 09 февраля 2015 года.

ДАННОЕ ПОЛОЖЕНИЕ ЯВЛЯЕТСЯ ОФИЦИАЛЬНЫМ ВЫЗОВОМ НА СОРЕВНОВАНИЯ!

Для справок: тел.: 8 (905) 569-03-46 Главный судья Кузнецов Борис

Web-pagehttp://tkmiem.ru/ leon2015 http://vk.com/tkmiem e-mail: [email protected]

 

CÚD

 

A	B	C	D	1Ú2	1®3	2®4	3Ú4
Выделенные строки таблицы показывают при каких значениях пропозициональных переменных (A, B, C и D) истинны посылки и заключение.   Л	Л	Л	Л	Л	И	И	Л
Л	Л	Л	И	Л	И	И	И
Л	Л	И	Л	Л	И	И	И
Л	Л	И	И	Л	И	И	И
Л	И	Л	Л	И	И	Л	Л
Л	И	Л	И	И	И	И	И
Л	И	И	Л	И	И	Л	И
Л	И	И	И	И	И	И	И
И	Л	Л	Л	И	Л	И	Л
И	Л	Л	И	И	Л	И	И
И	Л	И	Л	И	И	И	И
И	Л	И	И	И	И	И	И
И	И	Л	Л	И	Л	Л	Л
И	И	Л	И	И	Л	И	И
И	И	И	Л	И	И	Л	И
И	И	И	И	И	И	И	И

 

Пример: Если 2 - простое число (А), то это наименьшее простое число (В). Если 2 - наименьшее простое число, то 1 не простое число (С). Число 1 - не простое число. Следовательно, 2 -простое число. [7]

A®B; B®C; C

A.

Выделенная восьмая строка таблицы показывает при каких посылках истинно и заключение A	B	C	1®2	2®3
л	л	л	и	и
л	л	и	и	и
л	и	л	и	л
л	и	и	и	и
и	л	л	л	и
и	л	и	л	и
и	и	л	и	л
и	и	и	и	и

 

Приведенные примеры позволяют сформулировать некоторые правила записи сложных суждений. Так при записи сложных высказываний следует обращать внимание, чтобы в формулах не было двух рядом стоящих логичеcких связок - они долж­ны быть разъединены формулами либо вспомогательными символами и не было двух рядом стоящих формул - они должны быть разъединены логической связкой.

При записи сложных формул следует помнить, что

1) каждое вхождение логической связки “ ù” относится к пропозициональной переменной или формуле, следующей непосредственно за логической связкой справа;

2) каждое вхождение логической связки “ &” после расстановки скобок связывает пропозициональные переменные или формулы, непосредственно окружающие логическую связку;

3) каждое вхождение логической связки “ Ú;” после расстановки скобок связывает пропозициональные переменные или формулы, непосредственно окружающие эту связку и т.д.

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

Логические связки по силе и значимости могут быть упорядочены так: ù; &; Ú; ®; «. То есть самой сильной связкой является отрицание, затем коньюнкция, дизьюнкция, импликация и, наконец, эквиваленция. Зная правила о силе логических связок, можно опускать те пары скобок, без которых ясен порядок исполнения логических операций.

Пример: пусть дана формула F=(((F₁Ú(ùF₂))®F₃)«F₄).

Необходимо удалить скобки.

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

F=((F₁Ú(ùF₂))®F₃)«F₄;

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

F=(F₁Ú(ùF₂))®F₃«F₄;

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

F=F₁Ú(ùF₂)®F₃«F₄;

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

F=F₁ÚùF₂®F₃«F₄;

Итак, последовательность исполнения операций после задания значений пропозациональных переменных следующая: сначала необходимо определить значение формулы (ùF₂), затем (F₁Ú(ùF₂)) затем ((F₁Ú(ùF₂))®F₃) и, наконец, (((F₁Ú(ùF₂))®F₃)«F₄)

Пример: Дана формула F=F1&F2&F3ÚùF1®F3«F1. Необходимо расставить все скобки.

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

F1&F2&F3Ú(ùF1)®F3«F1;

2) поставить скобки на формулу, реализующую операцию конъюнкции:

F=((F1&F2)&F3)Ú(ùF1)®F3«F1;

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

F=(((F1&F2)&F3)Ú(ùF1))®F3«F1;

4) поставить скобки на формулу, реализующую операцию импликации:

F=((((F1&F2)&F3)Ú(ùF1))®F3)«F1;

5) поставить скобки на формулу, реализующую операцию эквиваленции:

F=(((((F1&F2)&F3)Ú(ùF1))®F3)«F1).

1.1.3 Законы алгебры логики

Две формулы F₁ и F₂ называются равносильными, если они имеют одинаковое значение “и” или “л” при одинаковых наборах пропозициональных переменных, включаемых в F₁ и F₂, т.е. F₁ = F₂. Если две формулы равносильны, то они эквивалентны, т.е. (F_i«F_i).

Если формула F имеет вхождением подфор­мулу F_i, для которой существует эквивалентная подформула F_j, т.е. F_i«F_j, то возможна подстановка всюду в формулу F вместо формулы F_i подформулу F_j без нарушения истинности формулы F.

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

 

 

Наименование закона	Равносильные формулы Fi=Fj
Коммутативности	(F1ÚF2)=(F2ÚF1); (F1&F2)=(F2&F1)
Ассоциативности	F1Ú(F2ÚF3)=(F1ÚF2)ÚF3; F1&(F2&F3) = (F1&F2)& F3
Дистрибутивности	F1Ú(F2 &F3)=(F1ÚF2)&(F1ÚF3); F1&(F2ÚF3)=F1&F2ÚF1&F3
Идемпотентности	FÚF = F; F&F = F
Исключенного третьего	FÚùF = и;
Противоречия	F&ùF = л
Де Моргана	ù(F1ÚF2) = ùF1&ùF2; ù(F1&F2) = ùF1ÚùF2 .
Поглощения	F1Ú(F1&F2) = F1; F1&(F1ÚF2) = F1
Дополнения	ù(ùF) = F
Свойства констант	FÚл = F; F&л= л; FÚи = и; F&и = F

 

Справедливость некоторых законов подтверждается в примерах таблицами истинности.

Пример: F₁Ú(F₁&F₂) = F₁

Сравните значения логических

функций в третьем и четвертом

столбцах. Так можно проверить

закон поглощения.

Пример: F₁ & (F₁ÚF₂) = F₁

Сравните значения логических

функций в третьем и четвертом

столбцах. Так можно проверить

второй закон поглощения.

F1 F2 ù (1Ú2) ù1&ù2         Л Л И И Л И Л Л И Л Л Л И И Л Л

Пример: ù(F₁ÚF₂) = ùF₁&ùF₂

Сравните значения логических

функций в третьем и четвертом

столбцах. Так можно проверить

закон де Моргана.

F1 F2 ù (1&2) ù1Úù2         Л Л И И Л И И И И Л И И И И Л Л

Пример: ù(F₁&F₂) = ùF₁ÚùF₂

Сравните значения логических

функций в третьем и четвертом

столбцах. Так можно проверить

второй закон де Моргана..

Пример: F₁Ú(F₂ &F₃)=(F₁ÚF₂)&(F₁ÚF₃).

 

Сравните значения логических функций в пятом и восьмом столбцах. Так можно проверить первый закон дистрибутивности.   F1	F2	F3	2&3	1Ú4	1Ú2	1Ú3	6&7
Л	Л	Л	Л	Л	Л	Л	Л
Л	Л	И	Л	Л	Л	И	Л
Л	И	Л	Л	Л	И	Л	Л
Л	И	И	И	И	И	И	И
И	Л	Л	Л	И	И	И	И
И	Л	И	Л	И	И	И	И
И	И	Л	Л	И	И	И	И
И	И	И	И	И	И	И	И

Пример: F₁&(F₂ÚF₃)=F₁&F₂ÚF₁&F₃

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

F1	F2	F3	2Ú3	1&4	1&2	1&3	6Ú7
Л	Л	Л	Л	Л	Л	Л	Л
Л	Л	И	И	Л	Л	Л	Л
Л	И	Л	И	Л	Л	Л	Л
Л	И	И	И	Л	Л	Л	Л
И	Л	Л	Л	Л	Л	Л	Л
И	Л	И	И	И	Л	И	И
И	И	Л	И	И	И	Л	И
И	И	И	И	И	И	И	И

 

 

1.1.4 Эквивалентные преобразования формул

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

Пример 26: F₁®F₂ = ùF₁ÚF₂ = ù(F₁&ùF₂).

 

Сравните значения логических функций в третьем, четвертом и пятом столбцах. То есть

операцию импликации всегда можно заместить исполнением операций дизьюнкции и отрицания или коньюнкции и отрицания.

Пример: F₁«F₂ = (F₁®F₂)&(F₂®F₁) = (ùF₁ÚF₂)&(ùF₂ÚF₁) =

= ù(ù(ùF₁ÚF₂) Úù(ùF₂ÚF₁)).

 

F1	F2	F1«F2	F1®F2	F2®F1	4&5	ùF1ÚF2	ùF2ÚF1	7&8	ù7Úù8	ù10
Л	Л	И	И	И	И	И	И	И	Л	И
Л	И	Л	И	Л	Л	И	Л	Л	И	Л
И	Л	Л	Л	И	Л	Л	И	Л	И	Л
И	И	И	И	И	И	И	И	И	Л	И

 

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

Пример: F₁«F₂ = ùF₁&ùF₂ÚF₁&F₂= ù(ù(ùF₁&ùF₂)&ù(F₁&F₂)).

 

Сравните значения логических функций в третьем, шестом и восьмом столбцах. Это значения трех эквивалентных функций.

F1	F2	1«2	ù1&ù2	1&2	4Ú5	ù4&ù5	ù7
Л	Л	И	И	Л	И	Л	И
Л	И	Л	Л	Л	Л	И	Л
И	Л	Л	Л	Л	Л	И	Л
И	И	И	Л	И	И	Л	И

 

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

Если формула F содержит подформулу F_i, то замена подформулы F_i в формуле F на эквивалент­ную ей формулу F_j не изменяет значения формулы F при любом наборе пропозициональных переменных. Если необходима подстановка в формулу F вместо формулы F_i новой формулы F_j, то эту операцию нужно выполнить всюду по символу F_i.

Правила замены и подстановки расширяют возможности эквива­лентных преобразований формул сложных высказываний.

Пример: Дано F=(F₁®F₂) ®((F₂®F₃) ®(F₁ÚF₂ ®F₃).

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

1) Удалить всюду логическую связку “®”:

F= ù(ùF₁ÚF₂)Ú(ù(ùF₂ÚF3)Ú(ù(F₁ÚF₂) ÚF₃);

2) Опустить отрицание на элементарные формулы по закону де Моргана:

F=F₁&ùF₂ÚF₂&ùF₃ÚùF₁&ùF₂ÚF₃;

3) Выполнить преобразование по закону дистрибутивности:

F=(F₁ÚùF₁) &ùF₂ÚF₂&ùF₃Ú F₃;

4) Удалить член (F₁ÚùF₁), так как (F₁ÚùF₁)=и:

F=ùF₂ÚF₂&ùF₃Ú F₃;

5) Выполнить преобразование по закону дистрибутивности:

F=ùF₂Ú(F₂ÚF3) &(ùF₃Ú F₃);

6) Удалить член (F₃ÚùF₃)=и:

F=ùF₂Ú(F₂ÚF3);

7) Применить закон ассоциативности:

F=(ùF₂ÚF₂)ÚF₃;

7) Приравнять “истине” значение формулы F, т.к. (ùF₂ÚF₂)=и:

F=иÚF₃=и.

Пример: Дано F=ù(F₁®F₂)&(ùF₃ÚùF₄)Úù(F₁ÚF₂)&ù(F₃&F₄).

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

1) Удалить логическую связку “®”:

F=ù(ùF₁ÚF₂)&(ùF₃ÚùF₄)Úù(F₁ÚF₂)&ù(F₃&F₄);

2) Опустить отрицание на элементарные формулы по закону де Моргана:

F=F₁&ùF₂&(ùF₃ÚùF₄)Ú ù F₁&ùF₂&(ùF₃ÚùF₄);

3) Выполнить преобразование по закону дистрибутивности:

F=(F₁Úù F₁) &ùF₂&(ùF₃ÚùF₄);

4) Удалить член (F₁ÚùF₁)=и:

F=ùF₂&(ùF₃ÚùF₄).

Дальнейшее упрощение формулы F невозможно.

 

Пример: Дано суждение "или верно, что Петр поступил в университет (А), и при этом неверно, что Петр не поступил и Андрей не поступил, или Петр поступил и Семен поступил (С), или даже Петр поступил и Семен поступил, и Андрей поступил (В)"[2].

Формула сложного высказывания имеет вид:

А&ù(ùA&ùВ)ÚА&СÚА&В&С;

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

А& (АÚВ)ÚА&СÚА&В&С;

2) применить закон идемпотентности:

А& (АÚВ)ÚA&А&СÚА&В&С;

3) применить закон дистрибутивности по переменной А:

А&((АÚВ)Ú А&СÚВ&С);

4) применить закон дистрибутивности по переменной С:

А&((АÚВ)Ú С&(АÚВ));

5) ввести константу "и":

А&((АÚВ)&”и”Ú С&(АÚВ));

6) применить закон дистрибутивности для подформулы (АÚВ):

А&(АÚВ)&(“и”ÚС);

7) удалить (“и”ÚС):

А&(АÚВ);

8) применить закон поглощения:

А.

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

 

Пример: Шесть школьников - Андрей, Борис, Григорий, Дмитрий, Евгений и Семен - участвовали в олимпиаде. Двое из них решили все задачи. На вопрос, кто решил все задачи, последовали ответы:1) Андрей и Дмитрий; 2) Борис и Евгений; 3) Евгений и Андрей; 4)Борис и Григорий; 5) Семен и Андрей. В четырех из этих ответов одна часть неверна, другая верна. В одном - обе части неверны. Кто решил все задачи? [2]

Введем обозначения:

A:= Андрей решил все задачи;

Б:= Борис решил все задачи;

Г:= Григорий решил все задачи;

Д:= Дмитрий решил все задачи;

Е:= Евгений решил все задачи;

С:= Семен решил все задачи.

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

ùA&ùД&(ùБ&ЕÚБ&ùЕ)&(ùЕ&АÚЕ&ùА)&(ùБ&ГÚБ&ùГ)&

(ùС&АÚС&ùА);

ùБ&ùЕ&(ùА&ДÚА&ùД) & (ùЕ&АÚЕ&ùА)&(ùБ&ГÚБ&ùГ)&

(ùС&АÚС&ùА);

ùЕ&ùА&(ùА&ДÚА&ùД)&(ùБ&ЕÚБ&ùЕ)&(ùБ&ГÚБ&ùГ)&

(ùС&АÚС&ùА);

ùБ&ùГ& (ùА&ДÚА&ùД)&(ùБ&ЕÚБ&ùЕ)&(ùЕ&АÚЕ&ùА)&

(ùС&АÚС&ùА);

ùС&ùА&(ùА&ДÚА&ùД)&(ùБ&ЕÚБ&ùЕ)&(ùЕ&АÚЕ&ùА)&

(ùБ&ГÚБ&ùГ).

Если допустить, что ùA=и и ùД=и, то первая формула может быть записана так:

ùA&ùД&(ùБ&ЕÚБ&ùЕ)&Е&ùА&(ùБ&ГÚБ&ùГ)&С&ùА,

т.к. член ùЕ&А=0.

Если допустить, что ùБ=и и ùЕ=и, то вторая формула может быть записана так:

ùБ&ùЕ&(ùА&ДÚА&ùД)&ùЕ&А&ùБ&Г&(ùС&АÚС&ùА),

т.к. члены Е&ùА=0 и Б&ùГ=0.

Если допустить, что ùЕ=и и ùА=и, то третья формула может быть записана так:

ùЕ&ùА&ùА&Д&Б&ùЕ&(ùБ&ГÚБ&ùГ)&С&ùА,

т.к. члены А&ùД=0, ùБ&Е=0, и ùС&А=0.

Если допустить, что ùБ=и и ùГ=и, то четвертая формула может быть записана так:

ùБ&ùГ&(ùА&ДÚА&ùД)&ùБ&Е&(ùЕ&АÚЕ&ùА)&(ùС&АÚС&ùА), т.к. член Б&ùЕ=0.

Если допустить, что ùС =и и ùА=и, то пятая формула может быть записана так:

ùС&ùА&ùА&Д&(ùБ&ЕÚБ&ùЕ)& Е&ùА&(ùБ&ГÚБ&ùГ),