Как решить логическое уравнение по информатике

Логические уравнения

В ЕГЭ (но не в учебниках) встречается тип заданий, которые до 2011 года имели один из двух видов:

• при каких значениях переменных a,b,c. данное выражение становится истинным(ложным);
• сколько различных решений имеет уравнение f(a,b,c. ) = 1 (0)

Это могут быть короткие выражения:

(K ^ L ^ M ) v (⌝L ^ ⌝M ^ N) = 0

((J → K) → (M /\ N /\ L)) /\ ((J /\ ¬K) → ¬(M /\ N /\ L)) /\ (M → J) = 1

(((J -> K) -> (M & N & L)) & ((J &

и системы однотипных или не совсем однотипных выражений.

в случае коротких выражений иногда проще всего построить таблицу истинности. Существуют онлайн-построители, например http://programming.dojo.net.nz/study/truth-table-generator/index

также можно писать несложные программы для построения таблиц истинности:

Проделывать многие операции над логическими выражениями умеет и WolframAlpha:

В целом дело сводится к анализу выражения, попыткам найти скрытую схему в нем.

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

Если это дизъюнкция, то могут быть рассуждения вида «если левая скобка 0, то правая обязана быть 1»

В демонстрационном варианте 2012 г., А ТАКЖЕ в реальных вариантах весны/лета 2011 года появилась новая формулировка:

Алгоритм решения системы с большим числом однотипных уравнений

1. преобразовать уравнения, найти что-то с известной таблицей истинности
2. проанализовать таблицу истинности. например, если получается XOR то либо первый аргумент 1 либо второй
3. метод гипотез: пусть х1 = 0, тогда при х2 = 0 получаем 00ххххххх, при х2 = 1 получаем 01ххххххх
4. первое уравнение дает N ветвей решений, нужно посмотреть что у них общего
5. так же разобрать второе уравнение, после чего должна проявиться закономерность построения решений
6. найти закономерность — определить, на сколько увеличилось число ветвей благодаря второму уравнению
7. подсчитать общее количество распространив эту схему до конца системы
8. может быть проще увидеть взаимосвязь всех уравнений вместе, как они определяют закономерность построения решения

2012 год

B15

Вот два способа рассуждения.

I.

Если обозначить A = x1 ≡ x2, B = x3 ≡ x4 и так далее

то получим: (A ∨ B) ∧ (¬A ∨ ¬B)

или, по закону Де Моргана, (A ∨ B) ∧ ¬(A ∧ B)

это достаточно известная альтернативная формула для исключающего ИЛИ, как и (A ∧ ¬B) ∧ (¬A ∧ B)

Тогда система принимает вид:

Из первого уравнения видно, что либо x1 и x2 одинаковы, либо x3 и x4 одинаковы.

то есть если x1 и x2 одинаковы, то x3 и x4 разные

и наоборот, если x1 и x2 различны, то x3 и x4 одинаковы

Иными словами, рассмотрим наборы при x1 = 0, тогда

если x2 = 0, то левая скобка 1, тогда правая скобка д.б. 0, т.е. либо x3,x4 = 0,1 либо 1,0,

если x2 = 1, то левая скобка 0, тогда правая скобка д.б. 1, т.е. либо x3=x4=0 либо x3=x4=1

получается четыре ветви

теперь рассмотрим наборы при x1 = 1, тогда

получается опять четыре ветви

то есть первое уравнение дает восемь «ветвей» решений

Что даст второе уравнение?

либо x3 и x4 одинаковы, либо либо x5 и x6 одинаковы

в каждой из 8 ветвей на некоторую пару x3,x4 приходится по две пары x5,x6

то есть второе уравнение даст 16 ветвей

Аналогично, третье уравнение даст 32 ветви,

а четвертое уравнение в каждой из них по два итоговых решения.

Итого — 64 решения.

II.

Если смотреть на систему как на целое, то можно получить общий вид цепочек

тогда не верно (x3 ≡x4), но верно (x5 ≡x6), не верно (x7 ≡x8) и верно (x9 ≡x10)

это наборы вида 00xx00xx00 00xx00xx11

в которых xx — это 01 или 10

Т.е. в каждом таком решении значения идут парами, если где-то пара одинаковая, то перед ней будет разная, и после будет разная.

8 групп комбинаций, в каждой из которых по 4 возможных значения на местах xx xx 8*4 = 32

И то же самое, если НЕ верно (x1 ≡x2)

Итого 64 решения.

Или можно чуть более наглядно это описать для тех, кто любит переобозначения.

Обозначим A0 = пара 00, A1 = пара 11, B0 = пара 01, B1 = пара 10

После любого A может идти только B и наоборот.

Рассмотрим комбинации по две:

A0B0 A0B1 A1B0 A1B1 B0A0 B0A1 B1A0 B1A1 — их получилось 8.

если их будет по три

то на каждую такую кобминацию будет по две трехбуквенных, то есть 16

если по четыре, то 32

Итого 64 решения.

2014 год

B15

Преобразуем уравнения к удобному виду:

(x1 ⊕ x2 ) ^ (x1 ⊕ x3) = 0

(x2 ⊕ x3 ) ^ (x2 ⊕ x4) = 0

(x8 ⊕ x9 ) ^ (x8 ⊕ x10) = 0

рассмотрим решения 0ххххххххх

(0 ⊕ x2 ) ^ (0 ⊕ x3) = 0

эти две скобки не должны быть одновременно 1, чтобы конъюнкция была 0

если левая скобка 1, то вторая д.б.0 и наоборот, и еще они могут быть равны 0 одновременно

итак если x2 = 1 то x3 = 0

если правая 1, то левая 0

а одновременно они нули — это 011ххххх

рассмотрим решения 1ххххххххх

(1 ⊕ x2 ) ^ (1 ⊕ x3) = 0

если х2 = 0, левая скобка 1, правая д.б. 0, т.е. х3 = 1

если х3 = 0, правая скобка 1, левая д.б.0, т.е. х2 = 1

и одновременно скобки нули при х2 = х3 = 1

итак, первое уравнение дает шесть ветвей решений

010xxxxxxx 001ххххххх 011ххххх

(1 ⊕ 0 ) ^ (1 ⊕ x4) = 0 (0 ⊕ 1 ) ^ (0 ⊕ x4) = 0 (1 ⊕ 1 ) ^ (1 ⊕ x4) = 0

0101хххххх 0010хххххх 0110хххххх

101ххххххх 110ххххххх 111ххххххх

(1 ⊕ 0 ) ^ (1 ⊕ x4) = 0 (0 ⊕ 1 ) ^ (0 ⊕ x4) = 0 (1 ⊕ 1 ) ^ (1 ⊕ x4) = 0

1010хххххх 1100хххххх 1110хххххх

итак второе уравнение дало 8 ветвей

третье должно дать 10

итак, ответ — 20 решений

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

2013 год

B15

преобразуем второе уравнение

все скобки здесь должны быть истинами

рассмотрим x1 = 1 и y1 = 1

т.е. комбинации 1xxx1xxx

(1 → x2) /\ (x2 → x3) /\ (x3 → x4) = 1

(1 → y2) /\ (y2 → y3) /\ (y3 → y4) = 1

(1 → 1) /\ (y2 → x2) /\ (y3 → x3) /\ (y4 →x4) = 1

это сразу определяет что x2 = 1, x3 = 1, x4 = 1 и то же для игреков

т.е. из этой ветви годится только решение 11111111

И (*) ВООБЩЕ если x_n = 1 то очевидно для всех i x_n+i = 1

и то же для всех y

т.е. если встречается 1, то далее все одноименные переменные тоже 1

01110111 например годится, 00110011 и 00010001

это следует из первых двух уравнений

а что дает третье уравнение?

то что если какой-то y=1 то однономерной x с ним тоже будет 1

т.е. ветви решений не симметричны:

годится 01110000 но не годится 00001111

подсчитаем комбинации исходя из этого

xx110011 (00, 01 и 11)

xxx10001 (000, 001, 011 и 111)

xxxx0000 (0000, 0001, 0011, 0111, 1111)

Ответ: 15

И еще примеры решения конкретных систем: Пример 1, Пример 2

Рассмотрим решение коротких и длинных одиночных уравнений

Два варианта решения:

• таблица истинности (гарантия верного ответа)
• аналитический (упрощение, сведение к системе)

АЛГОРИТМ аналитического решения

1. возможно решать противоположную задачу, определив общее число наборов,
2. в зависимости от необходимости превратить в конъюнкцию = 1 или дизъюнкцию = 0
3. разбить на систему
4. согласно таблице истинности описать наборы решений для каждой части системы
5. по возможности выбрать ту, где меньше решений
6. посмотреть какие решения совпадают, т.е. протестировать решения одной части для другой части
7. выкинуть из второй части то, что не является решениями первой части.
8. для системы из двух легко воспользоваться формулой количества пересечений.
9. иногда довольно легко подсчитать комбинации по их «правилу образования», иногда нагляднее и проще выписать их себе списком (если это в пределах десятка).

Рассмотрим пример: (K V L) → (L ^ M ^ N) = 0

Импликация. Ложна когда первая часть истинна, а вторая ложна. Отсюда система:

Первый вариант рассуждений. Рассмотрим антирешения.

дизъюнкция ложна в 4 случаях: 0000 0001 0010 0011

конъюнкция истинна в 2 случаях: 0111 1111

при этом эти «антирешения» не пересекаются, т.е. получается, что все остальные 16-6 = 10 комбинаций должны подходить обоим уравнениям. Потому что эти 10 комбинаций не содержат ни антирешений первого, ни антирешений второго уравнения.

Второй вариант рассуждений. Выберем уравнение с наименьшим числом решений, это первое (16-4 = 12).

Подставим эти решения во второе. Как это сделать, если у нас нет их полного списка?

Очень просто. Среди этих 12 решений есть 2 антирешения второго, так как она оба НЕ входят в 4 антирешения первого.

Значит их нужно выкинуть. 12-2 = 10

Третий вариант. Объединение множеств решений первого и второго — 16. Решений первого 12, решений второго 14.

А найти надо пересечения. По формуле мощности пересечения множеств

|X ∩ Y| = |X| + |Y| — |X U Y| = 12 + 14 — 16 = 26 — 16 = 10

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

( K | L ) | ( L & M & N )

0 0 0 0 | 1 0 0 0 1 0 0 0 0 0

0 0 0 1 | 1 0 0 0 1 0 0 0 0 1

0 0 1 0 | 1 0 0 0 1 0 0 1 0 0

0 0 1 1 | 1 0 0 0 1 0 0 1 0 1

0 1 0 0 | 0 0 1 1 0 1 0 0 0 0

0 1 0 1 | 0 0 1 1 0 1 0 0 0 1

0 1 1 0 | 0 0 1 1 0 1 1 1 0 0

0 1 1 1 | 0 0 1 1 1 1 1 1 1 1

1 0 0 0 | 0 1 1 0 0 0 0 0 0 0

1 0 0 1 | 0 1 1 0 0 0 0 0 0 1

1 0 1 0 | 0 1 1 0 0 0 0 1 0 0

1 0 1 1 | 0 1 1 0 0 0 0 1 0 1

1 1 0 0 | 0 1 1 1 0 1 0 0 0 0

1 1 0 1 | 0 1 1 1 0 1 0 0 0 1

1 1 1 0 | 0 1 1 1 0 1 1 1 0 0

1 1 1 1 | 0 1 1 1 1 1 1 1 1 1

Рассмотрим другой пример: (K v L) & (M v N) = 1

Первому не подходят 0000, 0001, 0010, 0011, т.е. решений 12

Второму не подходят 0000, 0100, 1000, 1100, т.е. решений 12

Объединение множеств решений первого и второго — 15,а не 16, так как комбинация 0000 не подходит обоим уравнениям..

|X ∩ Y| = |X| + |Y| — |X U Y| = 12 + 12 — 15 = 24 — 15 = 9

Или можно просто сказать, что уникальных антирешений всей системы 7 — они складываются из антирешений первого, антирешений второго минус 1 (одно) повторение антирешения 0000, 16-7 = 9

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

(K ^ L ^ M ) v (⌝L ^ ⌝M ^ N) = 0

Дизъюнкция равна 0, это система

16 комбинации всего возможны

антирешения первого: 111х, их два, следовательно 16-2 = 14 решений первого

антирешения второго: х001, их два, следовательно 16-2 = 14 решений второго

антирешения НЕ пересекаются

поэтому решений 14+14 — 16 = 12

(K v L v M ) ^ (⌝L ^ ⌝M ^ N) = 1

Здесь у второго вообще 2 решения (0001 и 1001), подставляем их в первое, 0001 является антирешением первого.

Ответ: 1 решение

(K ^ L ^ M ) → (⌝M ^ N) = 1

решим сначала (K ^ L ^ M ) → (⌝M ^ N) = 0

не противоречат ли они второй?

значит здесь 2 решения

значит у противоположной задачи 16 — 2 = 14 решений

Задания в 2010 году были в два раза длиннее. И переменных там больше.

Урок №6 Решение логических уравнений (10 класс)

Обращаем Ваше внимание, что в соответствии с Федеральным законом N 273-ФЗ «Об образовании в Российской Федерации» в организациях, осуществляющих образовательную деятельность, организовывается обучение и воспитание обучающихся с ОВЗ как совместно с другими обучающимися, так и в отдельных классах или группах.

Выберите документ из архива для просмотра:

Выбранный для просмотра документ Урок 6 Решение логических уравнений.doc

Тема урока: Решение логических уравнений

Образовательная – изучение способов решения логических уравнений, формирование умений и навыков решения логических уравнений и построения логического выражения по таблице истинности;

Развивающая — создать условия для развития познавательного интереса учащихся, способствовать развитию памяти, внимания, логического мышления;

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

Тип урока: комбинированный урок

Оборудование: компьютер, мультимедийный проектор, презентация 6.

Повторение и актуализацию опорных знаний. Проверка домашнего задания (10 минут)

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

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

1. Какое из приведенных слов удовлетворяет логическому условию:

(первая буква согласная→вторая буква согласная) ٨ (последняя буква гласная → предпоследняя буква гласная)? Если таких слов несколько, укажите наименьшее из них.

1) АННА 2) МАРИЯ 3) ОЛЕГ 4) СТЕПАН

А – первая буква согласная

В – вторая буква согласная

С – последняя буква гласная

D – предпоследняя буква гласная

Составим выражение:

2. Укажите, какое логическое выражение равносильно выражению

Упростим запись исходного выражения и предложенных вариантов:

3. Дан фрагмент таблицы истинности выражения F:

Какое выражение соответствует F?

Определим значения этих выражений при указанных значениях аргументов:

Ознакомление с темой урока, изложение нового материала (30 минут)

Мы продолжаем изучать основы логики и тема нашего сегодняшнего урока «Решение логических уравнений». Изучив данную тему, вы узнаете основные способы решения логических уравнений, получите навыки решения этих уравнений путем использования языка алгебры логики и умения составления логического выражения по таблице истинности.

1. Решить логическое уравнение

Ответ запишите в виде строки из четырех символов: значений переменных K, L, M и N (в указанном порядке). Так, например, строка 1101 соответствует тому, что K=1, L=1, M=0, N=1.

Преобразуем выражение (¬K  M) → (¬L  M  N)

Выражение ложно, когда оба слагаемые ложны. Второе слагаемое равно 0, если M =0, N =0, L =1. В первом слагаемом K =0, так как М=0, а .

2. Сколько решений имеет уравнение (в ответе укажите только число)?

Решение: преобразуем выражение

A + B =1 и C + D =1

2 способ: составление таблицы истинности

3 способ: построение СДНФ – совершенной дизъюнктивной нормальной формы для функции – дизъюнкции полных правильных элементарных конъюнкций.

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

Дополним конъюнкции до полных конъюнкций (произведение всех аргументов), раскроем скобки:

Учтем одинаковые конъюнкции:

В итоге получаем СДНФ, содержащую 9 конъюнкций. Следовательно, таблица истинности для данной функции имеет значение 1 на 9 строках из 2 4 =16 наборов значений переменных.

3. Сколько решений имеет уравнение (в ответе укажите только число)?

,

3 способ: построение СДНФ

Учтем одинаковые конъюнкции:

1

В итоге получаем СДНФ, содержащую 5 конъюнкций. Следовательно таблица истинности для данной функции имеет значение 1 на 5 строках из 2 4 =16 наборов значений переменных.

Построение логического выражения по таблице истинности:

для каждой строки таблицы истинности, содержащей 1 составляем произведение аргументов, причем, переменные, равные 0, входят в произведение с отрицанием, а переменные, равные 1 – без отрицания. Искомое выражение F будет составляется из суммы полученных произведений. Затем, если возможно, это выражение необходимо упростить.

Пример: дана таблица истинности выражения. Построить логическое выражение.

3. Задание на дом (5 минут)

Сколько решений имеет уравнение (в ответе укажите только число)?

По заданной таблице истинности составить логическое выражение и

Выбранный для просмотра документ Урок 6 Решение логических уравнений.ppt

Описание презентации по отдельным слайдам:

Проверка домашнего задания: Какое из приведенных слов удовлетворяет логическому условию: (первая буква согласная→вторая буква согласная) ٨ (последняя буква гласная → предпоследняя буква гласная)? Если таких слов несколько, укажите наименьшее. 1) АННА 2) МАРИЯ 3) ОЛЕГ 4) СТЕПАН 2. Укажите, какое логическое выражение равносильно выражению 3. Дан фрагмент таблицы истинности выражения F: Какое выражение соответствует F? xyzF 0001 0111 1100

Тема урока: Решение логических уравнений

1. Решить логическое уравнение (¬K  M) → (¬L  M  N) =0 Ответ запишите в виде строки из четырех символов: значений переменных K, L, M и N (в указанном порядке). Так, например, строка 1101 соответствует тому, что K=1, L=1, M=0, N=1.

3. Сколько решений имеет уравнение (в ответе укажите только число)? 1 способ: рассуждения Ответ: 9 2 способ: составление таблицы истинности ABCD АВСDA+BC+DF

3 способ: построение СДНФ – совершенной дизъюнктивной нормальной формы для функции – дизъюнкции полных конъюнкций. Преобразуем исходное выражение, раскроем скобки для того, чтобы получить дизъюнкцию конъюнкций: (A+B)*(C+D)=A*C+B*C+A*D+B*D= Дополним конъюнкции до полных конъюнкций (произведение всех аргументов), раскроем скобки:

4. Сколько решений имеет уравнение (в ответе укажите только число)?

Построение логического выражения по таблице истинности: для каждой строки таблицы истинности, содержащей 1 составляем произведение аргументов, причем, переменные, равные 0, входят в произведение с отрицанием, а переменные, равные 1 – без отрицания. Искомое выражение F будет составляется из суммы полученных произведений. Затем, если возможно, это выражение необходимо упростить. Пример: дана таблица истинности выражения. Построить логическое выражение. аbcF 0000 0010 0100 0110 1001 1011 1101 1110

Задание на дом: По заданной таблице истинности составить логическое выражение и упростить его. 2. Решить уравнение: 3. Сколько решений имеет уравнение? аbcF 0000 0010 0100 0111 1001 1011 1100 1111

Курс повышения квалификации

Дистанционное обучение как современный формат преподавания

• Сейчас обучается 930 человек из 80 регионов

Курс повышения квалификации

Инструменты онлайн-обучения на примере программ Zoom, Skype, Microsoft Teams, Bandicam

• Курс добавлен 31.01.2022
• Сейчас обучается 26 человек из 18 регионов

Курс повышения квалификации

Педагогическая деятельность в контексте профессионального стандарта педагога и ФГОС

• Сейчас обучается 36 человек из 23 регионов

Ищем педагогов в команду «Инфоурок»

Дистанционные курсы для педагогов

«Взбодрись! Нейрогимнастика для успешной учёбы и комфортной жизни»

Свидетельство и скидка на обучение каждому участнику

Найдите материал к любому уроку, указав свой предмет (категорию), класс, учебник и тему:

5 593 666 материалов в базе

Материал подходит для УМК

«Информатика (углублённый уровень) (в 2 частях)», Семакин И.Г., Шеина Т.Ю., Шестакова Л.В.

1.6.2. Логические формулы и функции

Самые массовые международные дистанционные

Школьные Инфоконкурсы 2022

33 конкурса для учеников 1–11 классов и дошкольников от проекта «Инфоурок»

«Психологические методы развития навыков эффективного общения и чтения на английском языке у младших школьников»

Свидетельство и скидка на обучение каждому участнику

Другие материалы

• 12.11.2017
• 2001
• 237

• 12.11.2017
• 708
• 1

• 12.11.2017
• 274
• 0

• 12.11.2017
• 980
• 8

• 12.11.2017
• 973
• 0

• 12.11.2017
• 377
• 0

• 12.11.2017
• 705
• 0

• 12.11.2017
• 796
• 0

Вам будут интересны эти курсы:

Оставьте свой комментарий

Авторизуйтесь, чтобы задавать вопросы.

Добавить в избранное

• 12.11.2017 16199
• RAR 112.9 кбайт
• 273 скачивания
• Рейтинг: 5 из 5
• Оцените материал:

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

Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете оставить жалобу на материал.

Автор материала

• На сайте: 4 года и 11 месяцев
• Подписчики: 0
• Всего просмотров: 96405
• Всего материалов: 15

Московский институт профессиональной
переподготовки и повышения
квалификации педагогов

Дистанционные курсы
для педагогов

663 курса от 690 рублей

Выбрать курс со скидкой

Выдаём документы
установленного образца!

Учителя о ЕГЭ: секреты успешной подготовки

Время чтения: 11 минут

В Ростовской и Воронежской областях организуют обучение эвакуированных из Донбасса детей

Время чтения: 1 минута

В ростовских школах рассматривают гибридный формат обучения с учетом эвакуированных

Время чтения: 1 минута

Курские власти перевели на дистант школьников в районах на границе с Украиной

Время чтения: 1 минута

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

Время чтения: 0 минут

Ленобласть распределит в школы прибывающих из Донбасса детей

Время чтения: 1 минута

В Белгородской области отменяют занятия в школах и детсадах на границе с Украиной

Время чтения: 0 минут

Подарочные сертификаты

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

Все материалы, размещенные на сайте, созданы авторами сайта либо размещены пользователями сайта и представлены на сайте исключительно для ознакомления. Авторские права на материалы принадлежат их законным авторам. Частичное или полное копирование материалов сайта без письменного разрешения администрации сайта запрещено! Мнение администрации может не совпадать с точкой зрения авторов.

Задача №23. Решение систем логических уравнений.

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

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

Сколь­ко су­ще­ству­ет раз­лич­ных на­бо­ров зна­че­ний ло­ги­че­ских пе­ре­мен­ных x1, х2, х3, х4, х5, х6, х7, х8, ко­то­рые удо­вле­тво­ря­ют всем пе­ре­чис­лен­ным ниже усло­ви­ям?

(x1 → х2) → (х3→ х4) = 1

(х3 → х4) → (х5 → х6) = 1

(х5 → х6) → (х7 → х8) = 1

В от­ве­те не нужно пе­ре­чис­лять все раз­лич­ные на­бо­ры зна­че­ний пе­ре­мен­ных x1, х2, х3, х4, х5, х6, х7, х8, при ко­то­рых вы­пол­не­на дан­ная си­сте­ма ра­венств. В ка­че­стве от­ве­та Вам нужно ука­зать ко­ли­че­ство таких на­бо­ров.

Сде­ла­ем за­ме­ну пе­ре­мен­ных:

(x1 → х2) = y1; (х3 → х4) = y2; (х5 → х6) = y3; (х7 → х8) = y4.

Тогда можно за­пи­сать си­сте­му в виде од­но­го урав­не­ния:

(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) = 1. Конъюнкция равна 1 (истинна), когда каждый операнд принимает значение 1. Т.е. каждая из импликаций должна быть истинна, а это выполняется при всех значениях, кроме (1 → 0). Т.е. в таблице значений переменных y1, y2, y3, y4 единица не должна стоять левее нуля:

Т.е. условия выполняются для 5 наборов y1-y4.

Т.к. y1 = x1 → x2, то значение y1 = 0 достигается на единственном наборе x1, x2: (1, 0), а значение y1 = 1 – на трех наборах x1, x2: (0,0) , (0,1), (1,1). Аналогично для y2, y3, y4.

Поскольку каждый набор (x1,x2) для переменной y1 сочетается с каждым набором (x3,x4) для переменной y2 и т.д., то количества наборов переменных x перемножаются:

Кол-во наборов на x1…x8

Сло­жим ко­ли­че­ство наборов: 1 + 3 + 9 + 27 + 81 = 121.

Сколько существует различных наборов значений логических переменных x1, x2, . x9, y1, y2, . y9, которые удовлетворяют всем перечисленным ниже условиям?

В ответе не нужно перечислять все различные наборы значений переменных x1, x2, . x9, y1, y2, . y9, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

Сде­ла­ем за­ме­ну пе­ре­мен­ных:

(x1 ≡ y1) = z1, (x2 ≡ y2) = z2,…. ,(x9 ≡ y9) = z9

Систему можно записать в виде одного уравнения:

(¬ z1 ≡ z2) ∧ (¬ z2 ≡ z3) ∧ …..∧ (¬ z8 ≡ z9)

Эквивалентность истинна, только если оба операнда равны. Решениями этого уравнения будут два набора:

Т.к. zi = (xi ≡ yi), то значению zi = 0 соответствуют два набора (xi,yi): (0,1) и (1,0), а значению zi = 1 — два набора (xi,yi): (0,0) и (1,1).

Тогда первому набору z1, z2,…, z9 соответствует 2 9 наборов (x1,y1), (x2,y2),…, (x9,y9).

Столько же соответствует второму набору z1, z2,…, z9. Тогда всего 2 9 +2 9 = 1024 наборов.

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

Этот метод применяется, если система уравнений достаточно проста и порядок увеличения количества наборов при добавлении переменных очевиден.

Сколь­ко раз­лич­ных ре­ше­ний имеет си­сте­ма урав­не­ний

где x1, x2, … x10 — ло­ги­че­ские пе­ре­мен­ные?

В от­ве­те не нужно пе­ре­чис­лять все раз­лич­ные на­бо­ры зна­че­ний x1, x2, … x10, при ко­то­рых вы­пол­не­на дан­ная си­сте­ма ра­венств. В ка­че­стве от­ве­та Вам нужно ука­зать ко­ли­че­ство таких на­бо­ров.

Решим первое уравнение. Дизъюнкция равна 1, если хотя бы один из ее операндов равен 1. Т.е. решениями являются наборы:

Для x1=0 существуют два значения x2 ( 0 и 1), а для x1=1 только одно значение x2 (1), такие, что набор (x1,x2) является решением уравнения. Всего 3 набора.

Добавим переменную x3 и рассмотрим второе уравнение. Оно аналогично первому, значит для x2=0 существуют два значения x3 ( 0 и 1), а для x2=1 только одно значение x3 (1), такие, что набор (x2,x3) является решением уравнения. Всего 4 набора.

Несложно заметить, что при добавлении очередной переменной добавляется один набор. Т.е. рекурсивная формула количества наборов на (i+1) переменных:

N_i+1 = N_i + 1. Тогда для десяти переменных получим 11 наборов.

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

Сколь­ко су­ще­ству­ет раз­лич­ных на­бо­ров зна­че­ний ло­ги­че­ских пе­ре­мен­ных x₁, . x₄, y₁. y₄, z₁. z₄, ко­то­рые удо­вле­тво­ря­ют всем пе­ре­чис­лен­ным ниже усло­ви­ям?

В от­ве­те не нужно пе­ре­чис­лять все раз­лич­ные на­бо­ры зна­че­ний пе­ре­мен­ных x₁, . x₄, y₁, . y₄, z₁, . z₄, при ко­то­рых вы­пол­не­на дан­ная си­сте­ма ра­венств.

В ка­че­стве от­ве­та Вам нужно ука­зать ко­ли­че­ство таких на­бо­ров.

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

Рассмотрим первое уравнение. Конъюнкция истинна (равна 1) только тогда, когда все ее операнды истинны (равны 1). Импликация равна 1 на всех наборах, кроме (1,0). Значит, решением первого уравнения будут такие наборы x1, x2, x3, x4, в которых 1 не стоит левее 0 (5 наборов):