Автор Тема: Как решить "логическую" задачу с помощью полиномов Жегалкина?  (Прочитано 1162 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Оффлайн Admin

  • Администратор
  • Сообщений: 4954
  • Поблагодарили: 1572 раз(а)
    • Просмотр профиля
Полиномы Жегалкина можно с успехом применять к решению так называемых логических задач. В задачах, именуемых логическими, обычно имеется несколько высказываний, относительно которых известно, что столько-то из них истинны, а столько-то ложны, но не известно, какие именно соответствуют действительности, а какие - нет. Пусть имеется \(  \large n \) высказываний, из которых \(  \large k \) истинно, \(  \large n−k \) - ложно. И пусть известны некоторые ограничения, связанные с этими высказываниями. Составим булевы функции, соответствующие этим высказываниям, представим их в полиномиальной форме и просуммируем по модулю два. Будем использовать простой факт из теории булевых функций, который назовём теоремой о сумме констант: сумма Жегалкина булевых функций равна единице, если количество слагаемых, равных единице, нечётно, и равна нулю в противном случае. Пусть \(  \large f \) - функция, являющаяся результатом суммирования. Если \(  \large k \) - чётное число, то \(  \large f=0 \), если нечётное - \(  \large f=1 \). Далее нужно проанализировать варианты распределения нулей и единиц, учитывая теорему о сумме констант и отбрасывая те варианты, что противоречат условию задачи (ограничения).

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

Решение. Введём булевы переменные \(  \large x_i,y_i,z_i, \ i=1,2,3 \). Пусть \(  \large x_i \) - "Александров занял \(  \large i \)-ое место", \(  \large y_i \) - "Васильев занял \(  \large i \)-ое место", \(  \large z_i \) - "Сергеев занял \(  \large i \)-ое место". Составим булевы функции, соответствующие высказываниям болельщиков, представим их в полиномиальной форме, просуммируем их по модулю два и приравняем к \(  \large 1 \), так как только одно из трёх высказываний истинно:

\(  \large x_1 \oplus z_3' \oplus y_1'=1 \ \Leftrightarrow \ x_1 \oplus z_3 \oplus 1 \oplus y_1 \oplus 1 =1  \ \Leftrightarrow x_1 \oplus y_1 \oplus z_3=1 \).

Cогласно теореме о сумме констант, такое равенство возможно, если одно слагаемое равно \(  \large 1 \) или все три слагаемых равны \(  \large 1 \). Проанализируем все варианты:

1) Если \(  \large x_1=1, \ y_1=z_3=0 \), то Александров занял первое место, Васильев занял второе или третье место, а Сергеев - первое или второе. Сергеев не может быть на первой ступени пьедестала, иначе двое заняли одно место. Значит, он занял второе место. Тогда Васильев на последней ступени пьедестала. Итак, сначала идёт Александров, потом Сергеев, затем Васильев. Но тогда угадали все болельщики, а это противоречит условию задачи.

2) Если \(  \large x_1=0, \ y_1=1, \ z_3=0 \), то Александров на втором или третьем месте, Васильев - на первом, Сергеев - на первом или втором. Учитывая, что двое участников, согласно условию задачи, не могут занять одно и то же место, получим следующее распределение мест: Васильев, Сергеев, Александров. Угадал только один болельщик. Этот вариант подходит.

3) Если \(  \large x_1=y_1=0, \ z_3=1 \), то Александров, как и Васильев, на втором или третьем месте, а Сергеев на  третьем месте. Тогда вершина пьедестала осталась не занятой, и двое заняли одно место. Это не соответствует условию задачи.

4) Если \(  \large x_1=y_1=z_3=1  \), то Александров и Васильев заняли первое место, а Сергеев оказался на третьей ступени пьедестала. Как и предыдущий, этот случай противоречит условию задачи.

Итак, Васильев был первым, вторым - Сергеев, а Александров занял третье место.
 

Оффлайн Admin

  • Администратор
  • Сообщений: 4954
  • Поблагодарили: 1572 раз(а)
    • Просмотр профиля
Пример 2. Следователь расследует кражу картины из музея. Есть трое подозреваемых - Егоров, Железякин, Зайцев, из которых виновен только один, а также двое свидетелей. В ходе допроса подозреваемых  и свидетелей были получены такие показания:
1) Картину украл Егоров или Железякин;
2) Егоров и Зайцев не причастны к краже;
3) Зайцев украл картину, а Егоров и Железякин не делали этого;
4) Егоров виновен, или виновны Железякин и Зайцев, или все трое не совершали кражи;
5) Егоров и Железякин не виновны, а Зайцев виновен, или Егоров и Зайцев не виновны, а Железякин виновен.
Следователь, ведущий дело, точно знает, что только трое сказали правду. Требуется найти виновного в краже.

Решение. Пусть \(  \large x \) - "Егоров украл картину", \(  \large y \) - "Железякин украл картину", \(  \large z \) - "Зайцев украл картину". Тогда показания подозреваемых и свидетелей можно формализовать следующим образом:

1) \(  \large x \vee y = xy \oplus x \oplus y \);

2) \(  \large x'z'=(x \oplus 1)(z \oplus 1)= xz \oplus z \oplus x \oplus 1 \);

3) \(  \large zx'y'=( x \oplus 1) (y \oplus 1)z=xyz \oplus yz \oplus xz \oplus z \);

4) \(  \large x \vee (yz) \vee (x'y'z') = xy \oplus xz \oplus y \oplus z \oplus 1 \);

5) \(  \large (x'y'z) \vee (x'yz')=xy \oplus xz \oplus z \oplus y \).

Так как правду сказали только трое, то, согласно теореме о сумме констант,

\(  \large xy \oplus x \oplus y \oplus xz \oplus z \oplus x \oplus 1 \oplus xyz \oplus yz \oplus xz \oplus z \oplus xy \oplus xz \oplus y \oplus z \oplus 1 \oplus xy \oplus xz \oplus z \oplus y=1 \ \Leftrightarrow \   \)

\(  \large \Leftrightarrow \ xyz \oplus yz  \oplus xy \oplus y=1 \)

Картину украл только один человек, значит, учитывая теорему о сумме констант, подходит только вариант, когда \(  \large xyz=0, \ yz=0, \ xy=0, \ y=1 \). Следовательно, кражу совершил Железякин.
 

Оффлайн Admin

  • Администратор
  • Сообщений: 4954
  • Поблагодарили: 1572 раз(а)
    • Просмотр профиля
Пример 3. Один из знатоков алгебры логики, приглашая к себе в гости приятеля, решил проверить его способности в решении логических задач. Он так описал код своего четырехкнопочного кодового замка: «Замок открывается, если выполняются следующие четыре условия: если не нажата кнопка 3, то нужно нажать кнопку 1 и не нажимать кнопку 4; если нажать кнопку 4, то нужно нажать кнопку 3 и не нажимать кнопку 2; не верно, что нужно нажать кнопку 2 или не нажимать кнопку 3, и все это притом, что не нажата кнопка 4; не нажимая кнопку 4, нажать кнопку 1 или кнопку 3». Приятель знатока решил задачу. Нажав какие кнопки, можно открыть замок?

Решение. Введём булевы переменные \(  \large x, y,z, t \). Поставим им в соответствие следующие высказывания: "Нажата первая кнопка", "Нажата вторая кнопка", "Нажата третья кнопка", "Нажата четвёртая кнопка". Тогда высказывания, фигурирующие в условии задачи, можно формализовать так:

1) \(  \large f_1 \equiv z' \to (xt') \);

2) \(  \large f_2 \equiv  t \to (zy') \);

3) \(  \large f_3 \equiv  t' \to (y \vee z')' \);

4) \(  \large f_4 \equiv t' \to (x \vee z) \).

Приведём указанные выше функции к полиномиальной форме:

1) \(  \large f_1=z \oplus xt \oplus x \oplus xzt \oplus xz \);

2) \(  \large f_2=t \oplus 1 \oplus yzt \oplus zt \);

3) \(  \large f_3=t \oplus yz \oplus z \oplus yzt \oplus zt \);

4) \(  \large f_4=xt \oplus t \oplus x \oplus z \oplus xzt \oplus zt \oplus xz \).

Все эти высказывания, согласно условию задачи, истинны, значит, сумма рассматриваемых булевых функций равна \(  \large 0 \), так как \(  \large 1 \oplus 1 \oplus 1 \oplus 1=0 \). Cледовательно,

\(  \large f_1 \oplus f_2 \oplus f_3 \oplus f_4 =0 \ \Leftrightarrow \ 1 \oplus yz \oplus zt \oplus z=0 \ \Leftrightarrow  yz \oplus zt \oplus z=1 \).

Это возможно тогда и только тогда, когда одно из слагаемых равно \(  \large 1 \), а два других - \(  \large 0 \). Рассмотрим всевозможные случаи:

1) Первый случай - \(  \large yz=0, \ zt=0, \ z=1 \). Значит, \(  \large y=0 \) или \(  \large y=1 \), \(  \large t=0 \) или \(  \large t=1 \), \(  \large z=1 \), а \(  \large x \) принимает любое значение (\(  \large 0 \) или \(  \large 1 \)). Итак, получаем следующие восемь вариантов распределений значений булевых переменных:

а) \(  \large x=y=0, \ z=1, \ t=0 \);

б) \(  \large x=y=0, \ z=t=1 \);

в) \(  \large x=1, \ y=0, \ z=1, \ t=0 \);

г) \(  \large x=1, \ y=0, \ z=t=1 \);

д) \(  \large x=y=z=1, \ t=0 \);

е) \(  \large x=y=z=t=1 \);

ж) \(  \large x=0, \ y=z=1, \ t=0 \);

з) \(  \large x=0, \ y=z=t=1  \).

Далее нужно подставить полученные значения в функции \(  \large f_1, \ f_2, \ f_3, \ f_4 \). Все они должны быть равны \(  \large 1 \). В случае, если хотя бы одна из функций равна \(  \large 0 \), данный набор значений булевых переменных отбрасывается как "лишний корень".

Выполним, например, проверку для первого набора. Пусть \(  \large x=y=0, \ z=1, \ t=0 \). Тогда \(  \large f_1=1' \to (0 \cdot 0')=1 \), \(  \large f_2= 0 \to (1 \cdot 0')=1 \), \(  \large f_3=0' \to (0 \vee 1')'=1 \), \(  \large f_4=0' \to ( 0 \vee 1)=1 \). Точно так же можно убедиться, что наборы \(  \large x=y=0, \ z=t=1 \); \(  \large x=1, \ y=0, \ z=1, \ t=0 \); \(  \large x=1, \ y=0, \ z=t=1 \) удовлетворяют условию задачи, а все остальные - нет.

Итак, замок открывается в следующих четырёх случаях:

а) нажата кнопка 3;

б) нажаты кнопки 3 и 4;

в) нажаты кнопки 1 и 3;

г) нажаты кнопки 1, 3 и 4.

2) Второй случай - \(  \large yz=0, \ zt=1, \ z=0 \). Это невозможно, так как условия \(  \large z=0 \) и \(  \large zt=1 \) несовместны.

3) Третий случай - \(  \large yz=1, \ zt=0, \ z=0 \). Также невозможно по причине несовместности условий \(  \large z=0 \) и \(  \large yz=1 \).
 

Оффлайн Admin

  • Администратор
  • Сообщений: 4954
  • Поблагодарили: 1572 раз(а)
    • Просмотр профиля
Пример 4. Один из трёх друзей, Алексеев, Быков, Васин, имеет собаку. Достоверно известно, что:
1) если Алексеев имеет собаку, то и у Быкова есть собака;
2) Алексеев - владелец собаки, или Васин - владелец собаки;
3) если Алексеев владеет собакой, то у Васина собаки нет.
Кто является владельцем собаки?

Решение. Введём булевы переменные - \(  \large x,y,z \). Пусть \(  \large x \) - Алексеев имеет собаку, \(  \large y \) - у Быкова есть собака, \(  \large z \) - Васин владеет собакой. Составим булевы функции, соответствующие высказываниям, фигурирующим в условии задачи, а потом представим эти функции в алгебраической нормальной форме:

1) \(  \large x \to y=x' \vee y= (x \oplus 1) \vee y =(x \oplus 1)y \oplus x \oplus 1 \oplus y=xy \oplus y \oplus x \oplus 1 \oplus y=xy \oplus x \oplus 1 \);

2) \(  \large x \vee z=xz \oplus x \oplus z \);

3) \(  \large x \to z'=x' \vee z'=(x \oplus 1) \vee (z \oplus 1)=(x \oplus 1)(z \oplus 1) \oplus x \oplus 1 \oplus z \oplus 1=xz \oplus z \oplus x \oplus 1 \oplus x \oplus z=xz \oplus 1 \).

Согласно условию задачи, высказывания, которым соответствуют данные функции, истинны. Значит, \(  \large xy \oplus x \oplus 1 \oplus xz \oplus x \oplus z \oplus xz \oplus 1=1 \ \Leftrightarrow xy \oplus z =1 \). Сумма Жегалкина булевых функций равна \(  \large 1 \) тогда и только тогда, когда количество слагаемых, равных \(  \large 1 \), нечётно. Следовательно, возможны два варианта:

1) \(  \large xy=0, \ z=1 \);

2) \(  \large xy=1, \ z=0 \).

Рассмотрим их подробно. Если \(  \large xy=0, \ z=1 \), то либо \(  \large x=y=0, \ z=1 \), либо \(  \large x=1, \ y=0, \ z=1 \), либо \(  \large x=0, \ y=1, \ z=1  \). В первом случае Васин имеет собаку, второй и третий случаи противоречат условию задачи, так как собака есть только у одного из друзей. Если \(  \large xy=1, \ z=0 \), то Алексеев и Быков - владельцы собаки, что противоречит условию задачи. Итак, собака есть у Васина.