Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015
Инфоурок / Информатика / Другие методич. материалы / Способ решения систем логических уравнений

Способ решения систем логических уравнений



57 вебинаров для учителей на разные темы
ПЕРЕЙТИ к бесплатному просмотру
(заказ свидетельства о просмотре - только до 11 декабря)


  • Информатика

Поделитесь материалом с коллегами:

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

Данная методика основана на использование таблиц истинности, рассчитана на учащихся, которые владеют методами преобразования логических выражений. Если учащиеся плохо владеют этими методами, можно использовать и без преобразований. (Мы будем использовать преобразования). Для овладения этим способом решения, необходимы в обязательном порядке знание свойств основных логических операций: конъюнкции, дизъюнкции, инверсии, импликации и эквивалентности.

Алгоритм решения систем уравнений по этому методу:

  1. Преобразовать логическое уравнение, упростить его.

  2. Определить последовательность решения уравнений в системе, так как в большинстве случаев идет последовательное решение уравнений сверху вниз (как они расположены в системе), но есть варианты, когда удобнее, проще начать решать снизу вверх.

  3. Построить таблицу переменных, где задать начальные значения первой переменной (или последней).

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

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

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



Пример1.

¬X1 ˅ X2=1

¬X2 ˅ X3=1

¬X3 ˅ X4=1

….

¬X9 ˅ X10=1

Начнем с Х1 и посмотрим какие значения эта переменная может принимать: 0 и 1.

Затем рассмотрим каждое из этих значений и посмотрим, какое может быть при этом Х2.

C:\Users\Админ\Desktop\семинар\ghj.jpg

Ответ: 11 решений

Пример 2.

(XX2)˅(¬X1˄¬X2)˅(X1↔X3)=1

(XX3)˅(¬X2˄¬X3)˅(X2↔X4)=1

(X8˄ X9)˅(¬X8˄¬X9)˅(X8↔X10)=0

Преобразуем по формуле (A˄ B)˅ (¬A ˄ ¬B)= AB

Получаем:

(X1↔X2) ˅ (X1↔ X3) =1

(X2↔X3) ˅ (X2↔ X4) =1

(X8↔X9) ˅ (X8↔ X10) =0

Возьмем Х1=0 и посмотрим какие значение может принимать Х2. Теперь для каждого Х2 рассмотрим какие значения может принимать Х3 и т.д.

C:\Users\Админ\Desktop\семинар\jjjj.jpg

Для Х1 =0 - 8 решений

Возьмем Х1=1 и посмотрим какие значение может принимать Х2. Теперь для каждого Х2 рассмотрим какие значения может принимать Х3 и т.д.

C:\Users\Админ\Desktop\семинар\jjjj77.jpg

Для Х1=1 – 8 решений

Итого 8+8=16 решений

Ответ. 16 решений

Пример 3.

¬ (X1↔X2) ˄ (X1 ˅ X3) ˄ (¬X1 ˅ ¬X3)=0

¬ (X2↔X3) ˄ (X2 ˅ X4) ˄ (¬X2 ˅ ¬X4)=0

.

¬ (X8↔X9) ˄ (X8 ˅ X10) ˄ (¬X8 ˅ ¬X10)=0

После преобразований (A˅ B) ˄(¬A ˅¬B)= ¬(AB)

получаем:

¬ (X1↔X2) ˄ ¬ (X1↔ X3)=0

¬ (X2↔X3) ˄ ¬ (X2↔ X4)=0

..

¬ (X8↔X9) ˄ ¬ (X8↔ X10)=0

Возьмем Х1=0 и посмотрим какие значение может принимать Х2. Теперь для каждого Х2 рассмотрим какие значения может принимать Х3 и т.д

C:\Users\Админ\Desktop\семинар\yui8.jpg

Получилось 10 решений для Х1=0

То же самое проделаем для Х1=1. Получим тоже 10 решений

Итого:10+10=20

Ответ: 20 решений.

Пример 4.

(Х1 ˄ Х2) ˅ (¬Х1 ˄ ¬Х2) ˅ (Х2 ˄ Х3) ˅ (¬Х2 ˄¬ Х3)=1

(Х2 ˄ Х3) ˅ (¬Х2 ˄ ¬Х3) ˅ (Х3˄ Х4) ˅ (¬Х3 ˄¬ Х4)=1

.

(Х8 ˄ Х9) ˅ (¬Х8˄ ¬Х9) ˅ (Х9 ˄ Х10) ˅ (¬Х9 ˄¬ Х10)=0

Преобразуем по формулам. (A˄ B)˅ (¬A ˄ ¬B)= AB. Получим:

(Х1↔ Х2) ˅ (Х2↔ Х3)=1

(Х2↔ Х3) ˅ (Х3↔ Х4)=1

(Х3↔ Х4) ˅ (Х4↔ Х5)=1

(Х4↔ Х5) ˅ (Х5↔ Х6)=1

(Х5↔ Х6) ˅ (Х6↔ Х7)=1

(Х6↔ Х7) ˅ (Х7↔ Х8)=1

(Х7↔ Х8) ˅ (Х8↔ Х9)=1

(Х8↔ Х9) ˅ (Х9↔ Х10)=0

Начнем с конца, потому что в последнем уравнении переменные определятся однозначно.

Пусть Х10=0, тогда Х9=1, Х8=0, Х7=0, Х6=0, а следующие переменные могут принимать разные значения. Будем рассматривать каждое.



hello_html_m453e6e7a.gif

Видим некоторую закономерность: Количество следующих решений равно сумме двух предыдущих.

Итого 21 решение для Х10=0

Теперь рассмотрим для Х10=1. Получаем тоже 21 решение

Итого:21+21=42

Ответ: 42 решения

Пример 5.

(X1 ˄ X2) ˅ (¬X1 ˄ ¬X2) ˅ (¬X3 ˄ X4) ˅ (X3 ˄ ¬X4)=1

(X3 ˄ X4) ˅ (¬X3 ˄ ¬X4) ˅ (¬X5 ˄ X6) ˅ (X5 ˄ ¬X6)=1

(X5 ˄ X6) ˅ (¬X5 ˄ ¬X6) ˅ (¬X7 ˄ X8) ˅ (X7 ˄ ¬X8)=1

(X7 ˄ X8) ˅ (¬X7 ˄ ¬X8) ˅ X9 ˄ X10) ˅ (X9˄ ¬X10)=1

Преобразуем по формулам: A ˄ B) ˅ (A ˄ ¬B)= A↔ ¬B

(A˄ B)˅ (¬A ˄ ¬B)= AB

(X1↔ X2) ˅ (X3 ↔ ¬X4)=1

(X3↔ X4) ˅ (X5 ↔ ¬X6)=1

(X5↔ X6) ˅ (X7 ↔ ¬X8)=1

(X7↔ X8) ˅ (X9 ↔ ¬X10)=1

Рассмотрим какие значения могут принимать Х1 и Х2: (0,0), (0,1), (1,0), (1,1).

Рассмотрим каждый вариант и посмотрим какие значения при этом могут принимать Х3, Х4

Начиная с Х7, Х8 будем сразу записывать количество решений, так как сразу видно, что когда значения одинаковые (1,1) и (0,0), то следующие переменные имеют 4 решения, а когда разные (0,1) и (1,0) – 2 решения.

C:\Users\Админ\Desktop\семинар\Безымянный1.jpg

Итого: 80+80+32=192

Ответ:192 решения

Пример 6.

(Х1↔ Х2) ˅ (Х2 ↔Х3)=1

(Х2↔ Х3) ˅ (Х3↔Х4)=1

(Х3↔ Х4) ˅ (Х4 ↔Х5)=1

.

(Х8↔ Х9) ˅ (Х9 ↔Х10)=1

Возьмем Х1=0 и посмотрим какие значение может принимать Х2. Теперь для каждого Х2 рассмотрим какие значения может принимать Х3 и т.д.

C:\Users\Админ\Desktop\семинар\Безымянный2.jpg

Видим некоторую закономерность: Количество следующих решений равно сумме двух предыдущих.

То же самое для Х1=1 получаем 89 решений

Итого: 89+89=178 решений

Ответ: 178 решений

Решим еще одним способом

(Х1↔ Х2) ˅ (Х2 ↔Х3)=1

(Х2↔ Х3) ˅ (Х3↔Х4)=1

(Х3↔ Х4) ˅ (Х4 ↔Х5)=1

.

(Х8↔ Х9) ˅ (Х9 ↔Х10)=1

Введем замену:

T1=(Х1↔ Х2)

T2=(Х2↔ Х3)

T3=(Х3↔ Х4)

T4=(Х4↔ Х5)

T5=(Х5↔ Х6)

T6=(Х6↔ Х7)

T7=(Х7↔ Х8)

T8=(Х8↔ Х9)

T9=(Х9↔ Х10)

Получаем:

T1 ˅ T2=1

T2 ˅ T3=1

T3 ˅ T4=1

T4 ˅ T5=1

T5 ˅ T6=1

T6 ˅ T7=1

T7 ˅ T8=1

T8 ˅ T9=1

T9 ˅ T10=1

Возьмем T1=1 и используем свойства дизъюнкции:

C:\Users\Админ\Desktop\семинар\666.jpg

НО Вспомним, что

T1=(Х1↔ Х2)

T2=(Х2↔ Х3) и т.д.

Воспользуемся свойством эквивалентности и убедимся, глядя на таблицу, что

Когда Т =1, то получается два решения. А когда =0 –одно решение.

Следовательно, можно подсчитать количество единиц и умножить их на 2+ количество нулей. Подсчет, так же используя закономерность.

C:\Users\Админ\Desktop\семинар\333.jpg

Получается, что количество единиц = предыдущему общему количеству решений Т, а количество нулей равно предыдущему количеству единиц

Итак. Получим. Так как единица дает два решения, то 34*2=68 решений из единицы+21 решение из 0.

Итого 89 решений для Т=1. Аналогичным способом получаем 89 решений для Т=0

Итого 89+89=178

Ответ: 178 решений

Пример 7.

(X1 ↔X2) ˅ (X3↔ X4) ˄ ¬(X1 ↔X2) ˅ ¬(X3↔ X4)=1

(X3 ↔X4) ˅ (X5↔ X6) ˄ ¬(X3 ↔X4) ˅ ¬(X5↔ X6)=1

(X5 ↔X6) ˅ (X7↔ X8) ˄ ¬(X5 ↔X6) ˅ ¬(X7↔ X8)=1

(X7 ↔X8) ˅ (X9↔ X10) ˄ ¬(X7 ↔X8) ˅ ¬(X9↔ X10)=1

Введем замену:

T1=(X1 ↔X2)

T2=(X3↔ X4)

T3=(X5↔ X6)

T4=(X7 ↔X8)

T5=(X9↔ X10)

Получим:

(Т1 ˅ Т2) ˄ ¬( Т1 ˅¬ Т2)=1

(Т2 ˅ Т3) ˄ ¬( Т2˅¬ Т3)=1

(Т3 ˅ Т4) ˄ ¬( Т3 ˅¬ Т4)=1

(Т4 ˅ Т5) ˄ ¬( Т4˅¬ Т5)=1

Рассмотрим какие могут быть Т:

Т1

Т2

Т3

Т4

Т5

Итого

0

1

0

1

0

32

1

0

1

0

1

32



ТK≠ТК+1 И ТKК+2

Получаем: 25=32 для Т

Итого: 32+32=64

Ответ: 64 решения.









57 вебинаров для учителей на разные темы
ПЕРЕЙТИ к бесплатному просмотру
(заказ свидетельства о просмотре - только до 11 декабря)


Краткое описание документа:

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

11 класса к ЕГЭ по информатике. Как показала практика подготовки учащихся к ЕГЭ - этим способом довольно

наглядно можно научиться решать такие задания.

Автор
Дата добавления 21.04.2015
Раздел Информатика
Подраздел Другие методич. материалы
Просмотров1139
Номер материала 248024
Получить свидетельство о публикации

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