Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 4 часа [ Летнее время ]


Решение логических задач

Решение логических задач


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


Отметим некоторые особенности решения "логических" задач методами алгебры высказываний. В таких задачах, как правило, имеется ряд высказываний, относительно которых известно, что столько-то из них истинны, а столько-то ложны, но не известно, какие именно истинны, а какие ложны. Например, имеется три высказывания [math]U,V,W[/math], из которых два истинны, а одно ложно. Учитывая эти условия, нужно составить из этих высказываний некое сложное высказывание, которое будет заведомо истинно (или ложно). Затем, используя законы логики, преобразовать его к виду, из которого определится ответ на вопрос задачи. В процессе равносильных преобразований использовать другие условия задачи. В рассматриваемом примере такое сложное высказывание строится исходя из следующих соображений. Так как из высказываний [math]U,V,W[/math] два истинны, то все дизъюнкции пар этих высказываний также будут истинны: [math]U\lor V,\, U\lor W,\, V\lor W[/math]. Следовательно, будет истинной и конъюнкция этих высказываний: [math](U\lor V)\land (U\lor W)\land (V\lor W)[/math]. Равносильное преобразование этого выражения будет зависеть от структуры высказываний [math]U,V,W[/math]. Разберем пример решения такой задачи.


Пример 7.16. Перед финалом школьного шахматного турнира, в который вышли Александров, Васин и Сергеев, один болельщик сказал, что первое место займет Александров, второй болельщик сказал, что Сергеев не будет последним, а третий — что Васину не занять первого места. После игр оказалось, что один болельщик ошибся, а два других угадали. Как распределились места, если никакие два участника не заняли одно и то же место?


Для решения введем следующие высказывания [math](i=1,2,3)\colon[/math]


[math]A_i:[/math] "Александров занял i-е место";
[math]B_i:[/math] "Васин занял i-е место";
[math]C_i:[/math] "Сергеев занял i-е место".

Тогда три высказывания болельщиков можно записать так:
1-й болельщик [math]U\colon~ A_1[/math];
2-й болельщик [math]V\colon~ \lnot C_3[/math];
3-й болельщик [math]W\colon~ \lnot B_1[/math].

Составим сложное высказывание, которое будет заведомо истинным. Так как из трех высказываний [math]U,V,W[/math] два высказывания истинны, то каждая из дизъюнкций [math]U\lor V,~ U\lor W,~ V\lor W[/math] будет истинной, а значит, истинной будет и их конъюнкция [math](U\lor V)\land (U\lor W)\land (V\lor W)[/math]. Преобразуем это высказывание равносильным образом:


[math]\begin{aligned}(U\lor V)\land (U\lor W)\land (V\lor W)&\cong (A_1\lor\lnot C_3)\land (A_1\lor\lnot B_1)\land (\lnot C_3\lor\lnot B_1) \cong\\[4pt] &\cong \bigl(A_1\lor (A_1\land\lnot B_1)\lor (\lnot C_3\land A_1)\lor (\lnot C_3\land\lnot B_1)\bigr) \land (\lnot C_3\lor\lnot B_1) \cong\\[4pt] &\cong \bigl(A_1\land (\lnot C_3\lor\lnot B_1)\bigr) \lor \bigl(A_1\land\lnot B_1\land (\lnot C_3\lor\lnot B_1)\bigr)\,\lor\\ &\phantom{\cong~}\lor \bigl(\lnot C_3\land A_1\land (\lnot C_3\lor\lnot B_1)\bigr)\lor \bigl(\lnot C_3\land \lnot B_1\land (\lnot C_3\lor\lnot B_1)\bigr) \cong\\[4pt] &\cong (A_1\land\lnot C_3)\lor (A_1\land\lnot B_1)\lor (A_1\land\lnot B_1)\lor (A_1\land\lnot C_3)\lor (\lnot B_1\land\lnot C_3) \cong\\[4pt] &\cong (A_1\land\lnot C_3)\lor (A_1\land\lnot B_1)\lor (\lnot B_1\land\lnot C_3).\end{aligned}[/math]

Полученное высказывание, представляющее собой дизъюнкцию некоторых высказываний, истинно. Следовательно, истинно по меньшей мере одно слагаемое. Рассмотрим последовательно все эти случаи:


1) [math]A_1\land\lnot C_3=1[/math]. Тогда [math]A_1=1[/math] и [math]\lnot C_3=1[/math], т.е. [math]C_3=0[/math]. Мы получаем следующее распределение мест: [math]ABC[/math];


2) [math]A_1\land\lnot B_1=1[/math]. Тогда [math]A_1=1[/math] и [math]\lnot B_1=1[/math], т. е. [math]B_1=0[/math]. Здесь мы получаем две возможности распределения мест: [math]ABC[/math] или [math]ACB[/math];


3) [math]\lnot B_1\land\lnot C_3[/math]. Тогда [math]\lnot B_1=1[/math] и [math]\lnot C_3[/math], т.е. [math]B_1=0[/math] и [math]C_3=0[/math]. Здесь варианты распределения такие: [math]ACB,~ CAB,~ CBA[/math].


В итоге получаем варианты ответов: [math]ACB,~ABC,~ CAB,~ CBA[/math]. Проверяя первый вариант, видим, что при нем истинными оказываются все три высказывания [math]U,V,W[/math] болельщиков, что не соответствует условию задачи. Окончательно получаем три решения: [math]ABC,~ CAB,~ CBA[/math].


Рассмотренный метод решения привел к получению своего рода "лишнего корня", что потребовало проверки полученных вариантов на соответствие условию задачи.


Рассмотрим более тонкий метод, который сразу даст только те ответы, которые удовлетворяют условию задачи. Он основан на составлении вместо высказывания [math](U\lor V)\land (U\lor W)\land (V\lor W)[/math] такого высказывания, которое более точно передает (описывает) суть условий задачи. Эта передача (описание) достаточно точна для того, чтобы не могло возникнуть никаких двусмысленностей и кривотолков.


Для составления такого высказывания кроме [math]U,V,W[/math] рассмотрим также высказывания:


[math]X:[/math] "1-й болельщик угадал";
[math]Y:[/math] "2-й болельщик угадал";
[math]Z:[/math] "3-й болельщик угадал".

Тогда нетрудно понять, что из двух высказываний [math]X\land U[/math] и [math]\lnot X\land\lnot U[/math] точно одно высказывание истинно. Значит, истинна и их дизъюнкция: [math](X\land U)\lor (\lnot X\land\lnot U)[/math]. Аналогично, истинны следующие высказывания, связанные со 2-м и 3-м болельщиками: [math](Y\land V)\lor (\lnot Y\land\lnot V)[/math] и [math](Z\land W)\lor (\lnot Z\land\lnot W)[/math]. Следовательно, истинна и конъюнкция всех этих трех высказываний:


[math]\bigl((X\land U)\lor (\lnot X\land\lnot U)\bigr)\lor \bigl((Y\land V)\lor (\lnot Y\land\lnot V)\bigr)\lor \bigl((Z\land W)\lor (\lnot Z\land\lnot W)\bigr).[/math]
(7.1)

Для преобразования этого высказывания нужно применить закон дистрибутивности конъюнкции относительно дизъюнкции. В итоге получится СДН-форма от переменных [math]X,Y,Z,U,V,W[/math]. Но многие ее совершенные конъюнктивные одночлены в силу условий задачи окажутся равными 0. Так как из трех высказываний [math]X,Y,Z[/math] точно два высказывания истинны, конъюнктивные одночлены, содержащие сомножители


[math]\lnot X\land \lnot Y\land Z,\quad X\land \lnot Y\land \lnot Z,\quad \lnot X\land Y\land \lnot Z,\quad \lnot X\land \lnot Y\land \lnot Z,[/math]

обратятся в 0. Так как из трех высказываний [math]X,Y,Z[/math] одно высказывание ложно, конъюнктивный одночлен, содержащий сомножитель [math]X\land Y\land Z[/math], также равен 0. В итоге в СДН-форме останутся лишь три совершенных конъюнктивных одночлена: это те, которые содержат сомножители


[math]X\land Y\land \lnot Z,\quad \lnot X\land Y\land Z,\quad X\land\lnot Y\land Z.[/math]

Данная СДН-форма имеет вид


[math](X\land Y\land\lnot Z\land U\land V\land\lnot W)\lor (\lnot X\land Y\land Z\land\lnot U\land V\land W)\lor (X\land\lnot Y\land Z\land U\land\lnot V\land W).[/math]

Для рассматриваемой задачи эта СДН-форма имеет вид


[math](X\land Y\land\lnot Z\land A_1\land\lnot C_3\land B_1)\lor (\lnot X\land Y\land Z\land\lnot A_1\land\lnot C_3\land\lnot B_1)\lor (X\land\lnot Y\land Z\land A_1\land C_3\land\lnot B_1).[/math]

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

1) [math]X\land Y\land\lnot Z\land A_1\land\lnot C_3\land B_1=1[/math]. Тогда [math]A_1=1,~ \lnot C_3=1[/math], а следовательно, [math]C_3=0[/math] и [math]B_1=1[/math]. Этот случай не может иметь места, так как [math]A[/math] и [math]B[/math] оказываются на первом месте;


2) [math]\lnot X\land Y\land Z\land\lnot A_1\land\lnot C_3\land\lnot B_1=1[/math]. Тогда [math]\lnot A_1=1,~ \lnot C_3=1,~ \lnot B_1=1[/math] и, следовательно, [math]A_1=0,~ C_3=0,~ B_1=0[/math], т. е. получаются две возможности распределения мест: [math]CAB,~ CBA[/math];


3) [math]X\land\lnot Y\land Z\land A_1\land C_3\land\lnot B_1=1[/math]. Тогда [math]A_1=1,~ C_3=1,~ \lnot B_1=1[/math], т.е. [math]B_1=0[/math] и получается следующее распределение мест: [math]ABC[/math].


Окончательно получаем три решения: [math]ABC,~ CAB,~ CBA[/math].


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




Пример 7.17. Решить задачу из предыдущего примера при условии, что результат финала угадал только один болельщик, а два Других ошиблись.


Решим сначала эту задачу более тонким методом. Для этого, как и в предыдущей задаче, составим высказывание (7.1). Отличие °т предыдущей задачи начнется в процессе преобразования этого высказывания, когда мы начнем учитывать новое условие задачи. В данном случае обратятся в 0 следующие конъюнктивные одночлены, входящие в полученную СДН-форму от переменных [math]X,Y,Z,U,V,W[/math]. Так как из трех высказываний [math]X,Y,Z[/math] точно два высказывания ложны, конъюнктивные одночлены, содержащие сомножители


[math]\lnot X\land Y\land Z,~ X\land\lnot Y\land Z,~ X\land Y\land\lnot Z[/math] обратятся в 0.

Так как из трех высказываний [math]X,Y,Z[/math] точно одно истинно, конъюнктивный одночлен, содержащий сомножитель [math]\lnot X\land\lnot Y\land\lnot Z[/math], также равен 0. В итоге в СДН-форме останутся только три совершенных конъюнктивных одночлена: это те, которые содержат сомножители


[math]X\land\lnot Y\land\lnot Z,\quad \lnot X\land Y\land\lnot Z,\quad \lnot X\land\lnot Y\land Z\,.[/math]

В данном случае СДН -форма имеет вид


[math]\begin{aligned}(X\land\lnot Y\land\lnot Z\land A_1\land C_3\land B_1)&\lor (\lnot X\land Y\land\lnot Z\land \lnot A_1\land\lnot C_3\land B_1) \lor\\ &\lor (\lnot X\land \lnot Y\land Z\land \lnot A_1\land C_3\land \lnot B_1).\end{aligned}[/math]

Полученное высказывание истинно. Значит, истинна по меньшей мере одна элементарная конъюнкция. Рассмотрим все эти случаи:


1) [math]X\land\lnot Y\land\lnot Z\land A_1\land C_3\land B_1=1[/math]. Тогда [math]A_1=1,~ C_3=1,~ B_1=1[/math]. Этот случай невозможен, так как [math]A[/math] и [math]B[/math] оказываются на первом месте;


2) [math]\lnot X\land Y\land\lnot Z\land \lnot A_1\land\lnot C_3\land B_1=1[/math]. Тогда [math]\lnot A_1=1,~ \lnot C_3=1,~ B_1=1[/math], т.е. [math]A_1=0,~ C_3=0[/math], и распределение мест следующее: [math]BCA[/math];


3) [math]\lnot X\land \lnot Y\land Z\land \lnot A_1\land C_3\land \lnot B_1=1[/math]. Тогда [math]\lnot A_1=1,~ \lnot C_3=1,~ \lnot B_1=1[/math], т.е. [math]A_1=0,~ B_1=0[/math].


Эти условия не могут быть выполнены: если [math]C[/math] на третьем месте, то из [math]A[/math] и [math]B[/math] один окажется на первом, что не так. Значит, этот случай также не может иметь места.


В итоге получаем следующее единственно возможное распределение мест: [math]BCA[/math].


При решении этой задачи более грубым методом (без введения высказываний [math]X,Y,Z[/math]) рассуждаем следующим образом. Так как из трех высказываний [math]U,V,W[/math] два высказывания ложны, каждая из конъюнкций [math]U\land V, U\land W, V\land W[/math] будет ложной, следовательно, ложной будет и их дизъюнкция:


[math](U\land V)\lor (U\land W)\lor (V\land W)\cong (A_1\land\lnot C_3)\lor (A_1\land B_1)\lor (\lnot B_1\land\lnot C_3)\cong[/math]

(это равносильное преобразование проделано в обратном направлении в начале решения предыдущего примера)

[math]\cong (A_1\lor\lnot C_3)\land (A_1\lor\lnot B_1)\land (\lnot B_1\lor\lnot C_3).[/math]

Полученное высказывание, представляющее собой конъюнкцию некоторых высказываний, ложно. Следовательно, ложен по меньшей мере один из сомножителей. Рассмотрим последовательно все эти случаи:


1) [math]A_1\lor\lnot C_3=0[/math]. Тогда [math]A_1=0[/math] и [math]\lnot C_3=0[/math], т.е. [math]C_3=1[/math] и получается следующее распределение мест: [math]BAC[/math];


2) [math]A_1\lor\lnot B_1=0[/math]. Тогда [math]A_1=0[/math] и [math]\lnot B_1=0[/math], т. е. [math]B_1=0[/math]. В данном случае получаем две возможности распределения мест: [math]BAC[/math] (уже была), [math]BCA[/math];


3) [math]\lnot B_1\lor\lnot C_3=0[/math]. Тогда [math]\lnot B_1=0[/math] и [math]\lnot C_3=0[/math], т.е. [math]B_1=1[/math] и [math]C_3=1[/math]. Получается один уже имеющийся вариант: [math]BAC[/math].


В итоге получим два варианта ответа: [math]BAC[/math] и [math]BCA[/math]. Проверка первого варианта на его соответствие условиям задачи показывает, что при нем ложными оказываются все три высказывания [math]U,V,W[/math] болельщиков, что не соответствует условию задачи. Окончательно получаем единственное решение: [math]BCA[/math].


Часовой пояс: UTC + 4 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2016 MathHelpPlanet.com. All rights reserved