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

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

1. Метод замены переменных.

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

Рассмотрим применение этого метода на конкретном примере.

Пример.

((X1 ≡ X2) ∧ (X3 ≡ X4)) ∨ (¬(X1 ≡ X2) ∧ ¬(X3 ≡ X4)) = 0

((X3 ≡ X4) ∧ (X5 ≡ X6)) ∨ (¬(X3 ≡ X4) ∧ ¬(X5 ≡ X6)) = 0

((X5 ≡ X6) ∧ (X7 ≡ X8)) ∨ (¬(X5 ≡ X6) ∧ ¬(X7 ≡ X8)) = 0

((X7 ≡ X8) ∧ (X9 ≡ X10)) ∨ (¬(X7 ≡ X8) ∧ ¬(X9 ≡ X10)) = 0

Решение:

Введем новые переменные: А=(X1 ≡ X2); В=(X3 ≡ X4); С=(X5 ≡ X6); D=(X7 ≡ X8); E=(X9 ≡ X10).

(Внимание! Каждая их переменных x1, x2, …, x10 должна входить только в одну из новых переменных А,В,С,D,Е, т.е. новые переменные независимы друг от друга).

Тогда система уравнений будет выглядеть так:

(А ∧ В) ∨ (¬А ∧ ¬В)=0

(В ∧ C) ∨ (¬B ∧ ¬C)=0

(С ∧ D) ∨ (¬C ∧ ¬D)=0

(D ∧ E) ∨ (¬D ∧ ¬E)=0

Построим дерево решений полученной системы:

Рассмотрим уравнение А=0, т.е. (X1 ≡ X2)=0. Оно имеет 2 корня:

		X1 ≡ X2

Из этой же таблицы видно, что уравнение А=1 тоже имеет 2 корня. Расставим кол-во корней на дереве решений:

Чтобы найти количество решений одной ветви, надо перемножить количества решений на каждом ее уровне. Левая ветвь имеет 2 ⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2=32 решения; правая ветвь имеет тоже 32 решения. Т.е. вся система имеет 32+32=64 решения.

Ответ: 64.

2. Метод рассуждений.

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

Пример 1. Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, которые удовлетворяют всем перечисленным ниже условиям?

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

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

x1\/y1 =1

В ответе не нужно перечислять все различные наборы значений переменных x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

Решение :

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

Чтобы представить дерево решений системы из первого и второго уравнений, надо каждую ветвь первого дерева продолжить деревом для переменных у . Построенное таким образом дерево будет содержать 36 ветвей. Некоторые из этих ветвей не удовлетворяют третьему уравнению системы. Отметим на первом дереве количество ветвей дерева «у» , которые удовлетворяют третьему уравнению:

Поясним: для выполнения третьего условия при х1=0 должно быть у1=1, т.е все ветви дерева «х» , где х1=0 можно продолжить только одной ветвью из дерева «у» . И только для одной ветви дерева «х» (правой) подходят все ветви дерева «у». Таким образом, полное дерево всей системы содержит 11 ветвей. Каждая ветвь представляет собой одно решение исходной системы уравнений. Значит, вся система имеет 11 решений.

Ответ: 11.

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

(X1 ≡ X2) ∨ (X1 ∧ X10) ∨ (¬X1 ∧ ¬ X10)= 1

(X2 ≡ X3) ∨ (X2 ∧ X10) ∨ (¬X2 ∧ ¬ X10)= 1.

………………

(X9 ≡ X10) ∨ (X9 ∧ X10) ∨ (¬X9 ∧ ¬ X10)= 1

(X1 ≡ X10) = 0

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

Решение : Упростим систему. Построим таблицу истинности части первого уравнения:

		X1 ∧ X10	¬X1 ∧ ¬ X10	(X1 ∧ X10) ∨ (¬X1 ∧ ¬ X10)

Обратите внимание на последний столбец, он совпадает с результатом действия X1 ≡ X10.

X1 ≡ X10

После упрощения получим:

(X1 ≡ X2) ∨ (X1 ≡ X10)=1

(X2 ≡ X3) ∨ (X2 ≡ X10)=1

(X3 ≡ X4) ∨ (X3 ≡ X10)=1

……

(X9 ≡ X10) ∨ (X9 ≡ X10)=1

(X1 ≡ X10) = 0

Рассмотрим последнее уравнение: (X1 ≡ X10) = 0 , т.е. х1 не должно совпадать с х10. Чтобы первое уравнение было равно 1, должно выполняться равенство (X1 ≡ X2)=1, т.е. х1 должно совпадать с х2.

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

Рассмотрим второе уравнение: при х10=1 и при х2=0 скобка должна быть равна 1 (т.е. х2 совпадает с х3); при х10=0 и при х2=1 скобка (X2 ≡ X10)=0 , значит, скобка (X2 ≡ X3) должна быть равна 1 (т.е. х2 совпадает с х3):

Рассуждая таким образом, построим дерево решений для всех уравнений:

Таким образом, система уравнений имеет всего 2 решения.

Ответ: 2.

Пример 3.

Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, y1, y2, y3, y4, z1, z2, z3, z4, которые удовлетворяют всем перечисленным ниже условиям?

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

(¬x1 /\ y1 /\ z1) \/ (x1 /\ ¬y1 /\ z1) \/ (x1 /\ y1 /\ ¬z1) = 1

(¬x2 /\ y2 /\ z2) \/ (x2 /\ ¬y2 /\ z2) \/ (x2 /\ y2 /\ ¬z2) = 1

(¬x3 /\ y3 /\ z3) \/ (x3 /\ ¬y3 /\ z3) \/ (x3 /\ y3 /\ ¬z3) = 1

(¬x4 /\ y4 /\ z4) \/ (x4 /\ ¬y4 /\ z4) \/ (x4 /\ y4 /\ ¬z4) = 1

Решение:

Построим дерево решений 1-го уравнения:

Рассмотрим второе уравнение:

• При х1=0 : вторая и третья скобки будут равны 0; чтобы первая скобка была равна 1, должны у1=1 , z1=1 (т.е. в этом случае - 1 решение)
• При х1=1 : первая скобка будет равна 0; вторая или третья скобка должна быть равна 1; вторая скобка будет равна 1 при у1=0 и z1=1; третья скобка будет равна 1 при у1=1 и z1=0 (т.е. в этом случае - 2 решения).

Аналогично для остальных уравнений. Отметим полученное кол-во решений у каждого узла дерева:

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

1 ветвь: 1 ⋅ 1 ⋅ 1 ⋅ 1 = 1 решение

2 ветвь: 1 ⋅ 1 ⋅ 1 ⋅ 2 =2 решения

3 ветвь: 1 ⋅ 1 ⋅ 2 ⋅ 2 =4 решения

4 ветвь: 1 ⋅ 2 ⋅ 2 ⋅ 2 =8 решения

5 ветвь: 2 ⋅ 2 ⋅ 2 ⋅ 2=16 решения

Сложим полученные числа: всего 31 решение.

Ответ: 31.

3. Закономерное увеличение количества корней

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

Пример 1. Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, которые удовлетворяют всем перечисленным ниже условиям?

¬(x1 ≡ x2) ∧ ((x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)) = 0

¬(x2 ≡ x3) ∧ ((x2 ∧ ¬x4) ∨ (¬x2 ∧ x4)) = 0

¬(x8 ≡ x9) ∧ ((x8 ∧ ¬x10) ∨ (¬x8 ∧ x10)) = 0

Упростим первое уравнение: (x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)=x1 ⊕ x3=¬(x1 ≡ x3). Тогда система примет вид:

¬(x1 ≡ x2) ∧ ¬(x1 ≡ x3) = 0

¬(x2 ≡ x3) ∧ ¬(x2 ≡ x4)= 0

¬(x8 ≡ x9) ∧ ¬(x8 ≡ x10) = 0

И т.д.

Каждое следующее уравнение имеет на 2 корня больше, чем предыдущее.

4 уравнение имеет 12 корней;

5 уравнение имеет 14 корней

8 уравнение имеет 20 корней.

Ответ: 20 корней.

Иногда количество корней растет по закону чисел Фибоначчи.

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

Как решать некоторые задачи разделов A и B экзамена по информатике

Урок №3. Логика. Логические функции. Решение уравнений

Большое количество задач ЕГЭ посвящено логике высказываний. Для решения большинства из них достаточно знания основных законов логики высказываний, знания таблиц истинности логических функций одной и двух переменных. Приведу основные законы логики высказываний.

1. Коммутативность дизъюнкции и конъюнкции:
   a ˅ b ≡ b ˅ a
   a ^ b ≡ b ^ a
2. Дистрибутивный закон относительно дизъюнкции и конъюнкции:
   a ˅ (b^с) ≡ (a ˅ b) ^(a ˅ с)
   a ^ (b ˅ с) ≡ (a ^ b) ˅ (a ^ с)
3. Отрицание отрицания:
   ¬(¬а) ≡ а
4. Непротиворечивость:
   a ^ ¬а ≡ false
5. Исключающее третье:
   a ˅ ¬а ≡ true
6. Законы де-Моргана:
   ¬(а ˅ b) ≡ ¬а ˄ ¬b
   ¬(а ˄ b) ≡ ¬а ˅ ¬b
7. Упрощение:
   a ˄ a ≡ a
   a ˅ a ≡ a
   a ˄ true ≡ a
   a ˄ false ≡ false
8. Поглощение:
   a ˄ (a ˅ b) ≡ a
   a ˅ (a ˄ b) ≡ a
9. Замена импликации
   a → b ≡ ¬a ˅ b
10. Замена тождества
    a ≡ b ≡(a ˄ b) ˅ (¬a ˄ ¬b)

Представление логических функций

Любую логическую функцию от n переменных – F(x 1 , x 2 , … x n) можно задать таблицей истинности. Такая таблица содержит 2 n наборов переменных, для каждого из которых задается значение функции на этом наборе. Такой способ хорош, когда число переменных относительно невелико. Уже при n > 5 представление становится плохо обозримым.

Другой способ состоит в том, чтобы задавать функцию некоторой формулой, используя известные достаточно простые функции. Система функций {f 1 , f 2 , … f k } называется полной, если любую логическую функцию можно выразить формулой, содержащей только функции f i .

Полной является система функций {¬, ˄, ˅}. Законы 9 и 10 являются примерами, демонстрирующими, как импликация и тождество выражается через отрицание, конъюнкцию и дизъюнкцию.

Фактически полной является и система из двух функций – отрицания и конъюнкции или отрицания и дизъюнкции. Из законов де-Моргана следуют представления, позволяющие выразить конъюнкцию через отрицание и дизъюнкцию и соответственно выразить дизъюнкцию через отрицание и конъюнкцию:

(а ˅ b) ≡ ¬(¬а ˄ ¬b)
(а ˄ b) ≡ ¬(¬а ˅ ¬b)

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

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

Рассмотрим несколько простых задач, связанных с логическими функциями.

Задача 15:

Дан фрагмент таблицы истинности. Какая из трех приведенных функций соответствует этому фрагменту?

X 1	X 2	X 3	X 4	F
1	1	0	0	1
0	1	1	1	1
1	0	0	1	0

1. (X 1 → X 2) ˄ ¬ X 3 ˅ X 4
2. (¬ X 1 ˄ X 2) ˅ (¬X 3 ˄ X 4)
3. ¬ X 1 ˅ X 2 ˅ (X 3 ˄ X 4)

Функция под номером 3.

Для решения задачи нужно знать таблицы истинности базовых функций и помнить о приоритетах операций. Напомню, что конъюнкция (логическое умножение) имеет более высокий приоритет и выполняется раньше, чем дизъюнкция (логическое сложение). При вычислениях нетрудно заметить, что функции с номерами 1 и 2 на третьем наборе имеют значение 1 и уже по этой причине фрагменту не соответствуют.

Задача 16:

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

(цифры, начиная со старшего разряда, идут в порядке убывания) → (число — четное) ˄ (младшая цифра – четная) ˄ (старшая цифра – нечетная)

Если таких чисел несколько, укажите наибольшее.

1. 13579
2. 97531
3. 24678
4. 15386

Условию удовлетворяет число под номером 4.

Первые два числа условию не удовлетворяют уже по той причине, что младшая цифра является нечетной. Конъюнкция условий ложна, если один из членов конъюнкции ложен. Для третьего числа не выполняется условие для старшей цифры. Для четвертого числа выполняются условия, накладываемые на младшую и старшую цифры числа. Первый член конъюнкции также истинен, поскольку импликация истинна, если ее посылка ложна, что имеет место в данном случае.

Задача 17: Два свидетеля дали следующие показания:

Первый свидетель: Если А виновен, то В и подавно виновен, а С – невиновен.

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

Какие заключения о виновности А, В и С можно сделать на основании свидетельских показаний?

Ответ: Из свидетельских показаний следует, что А и В виновны, а С – невиновен.

Решение: Конечно, ответ можно дать, основываясь на здравом смысле. Но давайте рассмотрим, как это можно сделать строго и формально.

Первое, что нужно сделать – это формализовать высказывания. Введем три логические переменные — А, В и С, каждая из которых имеет значение true (1), если соответствующий подозреваемый виновен. Тогда показания первого свидетеля задаются формулой:

A → (B ˄ ¬C)

Показания второго свидетеля задаются формулой:

A ˄ ((B ˄ ¬C) ˅ (¬B ˄ C))

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

Построим таблицу истинности для этих показаний:

A	B	C	F 1	F 2	F 1 ˄ F 2
0	0	0	1	0	0
0	0	1	1	0	0
0	1	0	1	0	0
0	1	1	1	0	0
1	0	0	0	0	0
1	0	1	0	1	0
1	1	0	1	1	1
1	1	1	0	0	0

Суммарные свидетельские показания истинны только в одном случае, приводящие к однозначному ответу – А и В виновны, а С – невиновен.

Из анализа этой таблицы также следует, что показания второго свидетеля более информативны. Из истинности его показания следует только два возможных варианта — А и В виновны, а С – невиновен или А и С виновны, а В – невиновен. Показания первого свидетеля менее информативны – существует 5 различных вариантов, соответствующих его показаниям. Совместно показания обоих свидетелей дают однозначный ответ о виновности подозреваемых.

Логические уравнения и системы уравнений

Пусть F(x 1 , x 2 , …x n) – логическая функция от n переменных. Логическое уравнение имеет вид:

F(x 1 , x 2 , …x n) = С,

Константа С имеет значение 1 или 0.

Логическое уравнение может иметь от 0 до 2 n различных решений. Если С равно 1, то решениями являются все те наборы переменных из таблицы истинности, на которых функция F принимает значение истина (1). Оставшиеся наборы являются решениями уравнения при C, равном нулю. Можно всегда рассматривать только уравнения вида:

F(x 1 , x 2 , …x n) = 1

Действительно, пусть задано уравнение:

F(x 1 , x 2 , …x n) = 0

В этом случае можно перейти к эквивалентному уравнению:

¬F(x 1 , x 2 , …x n) = 1

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

F 1 (x 1 , x 2 , …x n) = 1

F 2 (x 1 , x 2 , …x n) = 1

F k (x 1 , x 2 , …x n) = 1

Решением системы является набор переменных, на котором выполняются все уравнения системы. В терминах логических функций для получения решения системы логических уравнений следует найти набор, на котором истинна логическая функция Ф, представляющая конъюнкцию исходных функций F:

Ф = F 1 ˄ F 2 ˄ … F k

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

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

В предлагаемых на экзамене задачах решение обычно основано на учете специфики системы уравнений. Повторяю, кроме перебора всех вариантов набора переменных, общего способа решения задачи нет. Решение нужно строить исходя из специфики системы. Часто полезно провести предварительное упрощение системы уравнений, используя известные законы логики. Другой полезный прием решения этой задачи состоит в следующем. Нам интересны не все наборы, а только те, на которых функция Ф имеет значение 1. Вместо построения полной таблицы истинности будем строить ее аналог — бинарное дерево решений. Каждая ветвь этого дерева соответствует одному решению и задает набор, на котором функция Ф имеет значение 1. Число ветвей в дереве решений совпадает с числом решений системы уравнений.

Что такое бинарное дерево решений и как оно строится, поясню на примерах нескольких задач.

Задача 18

Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, которые удовлетворяют системе из двух уравнений?

Ответ: Система имеет 36 различных решений.

Решение: Система уравнений включает два уравнения. Найдем число решений для первого уравнения, зависящего от 5 переменных – x 1 , x 2 , …x 5 . Первое уравнение можно в свою очередь рассматривать как систему из 5 уравнений. Как было показано, система уравнений фактически представляет конъюнкцию логических функций. Справедливо и обратное утверждение, — конъюнкцию условий можно рассматривать как систему уравнений.

Построим дерево решений для импликации (x1→ x2) — первого члена конъюнкции, который можно рассматривать как первое уравнение. Вот как выглядит графическое изображение этого дерева:

Дерево состоит из двух уровней по числу переменных уравнения. Первый уровень описывает первую переменную X 1 . Две ветви этого уровня отражают возможные значения этой переменной – 1 и 0. На втором уровне ветви дерева отражают только те возможные значения переменной X 2 , для которых уравнение принимает значение истина. Поскольку уравнение задает импликацию, то ветвь, на которой X 1 имеет значение 1, требует, чтобы на этой ветви X 2 имело значение 1. Ветвь, на которой X 1 имеет значение 0, порождает две ветви со значениями X 2 , равными 0 и 1. Построенное дерево задает три решения, на которых импликация X 1 → X 2 принимает значение 1. На каждой ветви выписан соответствующий набор значений переменных, дающий решение уравнения.

Вот эти наборы: {(1, 1), (0, 1), (0, 0)}

Продолжим построение дерева решений, добавляя следующее уравнение, следующую импликацию X 2 → X 3 . Специфика нашей системы уравнений в том, что каждое новое уравнение системы использует одну переменную из предыдущего уравнения, добавляя одну новую переменную. Поскольку переменная X 2 уже имеет значения на дереве, то на всех ветвях, где переменная X 2 имеет значение 1, переменная X 3 также будет иметь значение 1. Для таких ветвей построение дерева продолжается на следующий уровень, но новые ветви не появляются. Единственная ветвь, где переменная X 2 имеет значение 0, даст разветвление на две ветви, где переменная X 3 получит значения 0 и 1. Таким образом, каждое добавление нового уравнения, учитывая его специфику, добавляет одно решение. Исходное первое уравнение:

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
имеет 6 решений. Вот как выглядит полное дерево решений для этого уравнения:

Второе уравнение нашей системы аналогично первому:

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

Разница лишь в том, что в уравнении используются переменные Y. Это уравнение также имеет 6 решений. Поскольку каждое решение для переменных X i может быть скомбинировано с каждым решением для переменных Y j , то общее число решений равно 36.

Заметьте, построенное дерево решений дает не только число решений (по числу ветвей), но и сами решения, выписанные на каждой ветви дерева.

Задача 19

Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, которые удовлетворяют всем перечисленным ниже условиям?

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1
(x1→y1) = 1

Эта задача является модификацией предыдущей задачи. Разница в том, что добавляется еще одно уравнение, связывающее переменные X и Y.

Из уравнения X 1 → Y 1 следует, что когда X 1 имеет значение 1(одно такое решение существует), то и Y 1 имеет значение 1. Таким образом, существует один набор, на котором X 1 и Y 1 имеют значения 1. При X 1 , равном 0, Y 1 может иметь любое значение, как 0, так и 1. Поэтому каждому набору с X 1 , равном 0, а таких наборов 5, соответствует все 6 наборов с переменными Y. Следовательно, общее число решений равно 31.

Задача 20

(¬X 1 ˅ X 2) ˄ (¬X 2 ˅ X 3) ˄ (¬X 3 ˅ X 4) ˄ (¬X 4 ˅ X 5) ˄ (¬X 5 ˅ X 1) = 1

Решение: Вспоминания основные эквивалентности, запишем наше уравнение в виде:

(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 5) ˄ (X 5 → X 1) = 1

Циклическая цепочка импликаций означает тождественность переменных, так что наше уравнение эквивалентно уравнению:

X 1 ≡ X 2 ≡ X 3 ≡ X 4 ≡ X 5 = 1

Это уравнение имеет два решения, когда все X i равны либо 1, либо 0.

Задача 21

(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 2) ˄ (X 4 → X 5) = 1

Решение: Так же, как и в задаче 20, от циклических импликаций перейдем к тождествам, переписав уравнение в виде:

(X 1 → X 2) ˄ (X 2 ≡ X 3 ≡ X 4) ˄ (X 4 → X 5) = 1

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

Задача 22

Сколько решений имеет следующая система уравнений?

((X 1 ≡ X 2) ˄ (X 3 ≡ X 4)) ˅(¬(X 1 ≡ X 2) ˄ ¬(X 3 ≡ X 4)) = 0

((X 3 ≡ X 4) ˄ (X 5 ≡ X 6)) ˅(¬(X 3 ≡ X 4) ˄ ¬(X 5 ≡ X 6)) = 0

((X 5 ≡ X 6) ˄ (X 7 ≡ X 8)) ˅(¬(X 5 ≡ X 6) ˄ ¬(X 7 ≡ X 8)) = 0

((X 7 ≡ X 8) ˄ (X 9 ≡ X 10)) ˅(¬(X 7 ≡ X 8) ˄ ¬(X 9 ≡ X 10)) = 0

Ответ: 64

Решение: Перейдем от 10 переменных к 5 переменным, введя следующую замену переменных:

Y 1 = (X 1 ≡ X 2); Y 2 = (X 3 ≡ X 4); Y 3 = (X 5 ≡ X 6); Y 4 = (X 7 ≡ X 8); Y 5 = (X 9 ≡ X 10);

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

(Y 1 ˄ Y 2) ˅ (¬Y 1 ˄ ¬Y 2) = 0

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

(Y 1 ≡ Y 2) = 0

Переходя к традиционной форме, запишем систему после упрощений в виде:

¬(Y 1 ≡ Y 2) = 1

¬(Y 2 ≡ Y 3) = 1

¬(Y 3 ≡ Y 4) = 1

¬(Y 4 ≡ Y 5) = 1

Дерево решений для этой системы простое и состоит из двух ветвей с чередующимися значениями переменных:

Возвращаясь к исходным переменным X, заметим, что каждому значению переменной Y соответствует 2 значения переменных X, поэтому каждое решение в переменных Yпорождает 2 5 решений в переменных X. Две ветви порождают 2 * 2 5 решений, так что общее число решений равно 64.

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

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

Если задачу трудно решить вручную, то можно поручить решение задачи компьютеру, написав соответствующую программу решения уравнений и систем уравнений.

Написать такую программу несложно. Такая программа легко справится со всеми задачами, предлагаемыми в ЕГЭ.

Как это ни странно, но задача нахождения решений систем логических уравнений является сложной и для компьютера, оказывается и у компьютера есть свои пределы. Компьютер может достаточно просто справиться с задачами, где число переменных 20 -30, но начнет надолго задумываться на задачах большего размера. Дело в том, что функция 2 n , задающая число наборов, является экспонентой, быстро растущей с увеличением n. Настолько быстро, что обычный персональный компьютер за сутки не справится с задачей, у которой 40 переменных.

Программа на языке C# для решения логических уравнений

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

Идея построения программы проста, — она основана на полном переборе всех возможных наборов значений переменных. Поскольку для заданного логического уравнения или системы уравнений число переменных n известно, то известно и число наборов – 2 n , которые требуется перебрать. Используя базовые функции языка C# — отрицание, дизъюнкцию, конъюнкцию и тождество, нетрудно написать программу, которая для заданного набора переменных вычисляет значение логической функции, соответствующей логическому уравнению или системе уравнений.

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

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

Вот как выглядит функция на языке C#, решающая нашу задачу:

///

/// программа подсчета числа решений

/// логического уравнения (системы уравнений)

///

///

/// логическая функция — метод,

/// сигнатура которого задается делегатом DF

///

/// число переменных

/// число решений

static int SolveEquations(DF fun, int n)

bool set = new bool[n];

int m = (int)Math.Pow(2, n); //число наборов

int p = 0, q = 0, k = 0;

//Полный перебор по числу наборов

for (int i = 0; i < m; i++)

//Формирование очередного набора — set,

//заданного двоичным представлением числа i

for (int j = 0; j < n; j++)

k = (int)Math.Pow(2, j);

//Вычисление значения функции на наборе set

Для понимания программы, надеюсь, достаточно сделанных объяснений идеи программы и комментариев в ее тексте. Остановлюсь лишь на пояснении заголовка приведенной функции. У функции SolveEquations два входных параметра. Параметр fun задает логическую функцию, соответствующую решаемому уравнению или системе уравнений. Параметр n задает число переменных функции fun. В качестве результата функция SolveEquations возвращает число решений логической функции, то есть число тех наборов, на которых функция принимает значение true.

Для школьников привычно, когда у некоторой функции F(x) входным параметром x является переменная арифметического, строкового или логического типа. В нашем случае используется более мощная конструкция. Функция SolveEquations относится к функциям высшего порядка – функциям типа F(f), у которых параметрами могут быть не только простые переменные, но и функции.

Класс функций, которые могут передаваться в качестве параметра функции SolveEquations, задается следующим образом:

delegate bool DF(bool vars);

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

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

class ProgramCommon

delegate bool DF(bool vars);

static void Main(string args)

Console.WriteLine(«У Функции And решений — » +

SolveEquations(FunAnd, 2));

Console.WriteLine(«У Функции 51 решений — » +

SolveEquations(Fun51, 5));

Console.WriteLine(«У Функции 53 решений — » +

SolveEquations(Fun53, 10));

static bool FunAnd(bool vars)

return vars && vars;

static bool Fun51(bool vars)

f = f && (!vars || vars);

f = f && (!vars || vars);

f = f && (!vars || vars);

f = f && (!vars || vars);

f = f && (!vars || vars);

static bool Fun53(bool vars)

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && (!((vars == vars) || (vars == vars)));

Вот как выглядят результаты решения по этой программе:

10 задач для самостоятельной работы

1. Какие из трех функций эквивалентны:
   1. (X → Y) ˅ ¬Y
   2. ¬(X ˅ ¬Y) ˄ (X → ¬Y)
   3. ¬X ˄ Y
2. Дан фрагмент таблицы истинности:

X 1	X 2	X 3	X 4	F
1	0	0	1	1
0	1	1	1	1
1	0	1	0	0

Какой из трех функций соответствует этот фрагмент:

1. (X 1 ˅ ¬X 2) ˄ (X 3 → X 4)
2. (X 1 → X 3) ˄ X 2 ˅ X 4
3. X 1 ˄ X 2 ˅ (X 3 → (X 1 ˅ X 4))
4. В состав жюри входят три человека. Решение принимается, если за него голосует председатель жюри, поддержанный хотя бы одним из членов жюри. В противном случае решение не принимается. Постройте логическую функцию, формализующую процесс принятия решения.
5. X выигрывает у Y, если при четырех бросаниях монеты трижды выпадает «орёл». Задайте логическую функцию, описывающую выигрыш X.
6. Слова в предложении нумеруются, начиная с единицы. Предложение считается правильно построенным, если выполняются следующие правила:
   1. Если четное в нумерации слово заканчивается на гласную, то следующее слово, если оно существует, должно начинаться с гласной.
   2. Если нечетное в нумерации слово заканчивается согласной, то следующее слово, если оно существует, должно начинаться с согласной и заканчиваться гласной.
      Какие из следующих предложений правильно построены:
   3. Мама мыла Машу мылом.
   4. Лидер всегда является образцом.
   5. Правда хорошо, а счастье лучше.
7. Сколько решений имеет уравнение:
   (a ˄ ¬ b) ˅ (¬a ˄ b) → (c ˄ d) = 1
8. Перечислите все решения уравнения:
   (a → b) → c = 0
9. Сколько решений имеет следующая система уравнений:
   X 0 → X 1 ˄ X 1 → X 2 = 1
   X 2 → X 3 ˄ X 3 → X 4 = 1
   X 5 → X 6 ˄ X 6 → X 7 = 1
   X 7 → X 8 ˄ X 8 → X 9 = 1
   X 0 → X 5 = 1
10. Сколько решений имеет уравнение:
    ((((X 0 → X 1) → X 2) → X 3) →X 4) →X 5 = 1

Ответы к задачам:

1. Эквивалентными являются функции b и c.
2. Фрагмент соответствует функции b.
3. Пусть логическая переменная P принимает значение 1, когда председатель жюри голосует «за» принятие решения. Переменные M 1 и M 2 представляют мнение членов жюри. Логическая функция, задающая принятие положительного решения может быть записана так:
   P ˄ (M 1 ˅ M 2)
4. Пусть логическая переменная P i принимает значение 1, когда при i-м бросании монеты выпадает «орёл». Логическая функция, задающая выигрыш X может быть записана так:
   ¬((¬P 1 ˄ (¬P 2 ˅ ¬P 3 ˅ ¬P 4)) ˅
   (¬P 2 ˄ (¬P 3 ˅ ¬P 4)) ˅
   (¬P 3 ˄ ¬P 4))
5. Предложение b.
6. Уравнение имеет 3 решения: (a = 1; b = 1; c = 0); (a = 0; b = 0; c = 0); (a = 0; b = 1; c = 0)

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

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

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

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

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

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

Ход урока

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

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

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

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

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

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

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

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

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

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

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

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

Составим таблицу:

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

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

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

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

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

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

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

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

(¬K  M) → (¬L  M  N) =0

Ответ запишите в виде строки из четырех символов: значений переменных 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, а
.

Ответ: 0100

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

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

(A +B )*(C +D )=1

A +B =1 и C +D =1

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

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

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

(A+B)*(C+D)=A*C+B*C+A*D+B*D=

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

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

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

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

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

,

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

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

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

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

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

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

Решение:

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

Решить уравнение:

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

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

упростить его.

Данной материал содержит презентацию, в которой представлены методы решения логических уравнений и систем логических уравнений в задании В15 (№ 23, 2015) ЕГЭ по информатике. Известно, что это задание является одним из самых сложных среди заданий ЕГЭ. Презентация может быть полезна при проведении уроков по теме "Логика" в профильных классах, а также при подготовке к сдаче ЕГЭ.

Скачать:

Предварительный просмотр:

Чтобы пользоваться предварительным просмотром презентаций создайте себе аккаунт (учетную запись) Google и войдите в него: https://accounts.google.com

Подписи к слайдам:

Решение задания В15 (системы логических уравнений) Вишневская М.П., МАОУ «Гимназия №3» 18 ноября 2013 г., г. Саратов

Задание В15 - одно из самых сложных в ЕГЭ по информатике!!! Проверяются умения: преобразовывать выражения, содержащие логические переменные; описывать на естественном языке множество значений логических переменных, при которых заданный набор логических переменных истинен; подсчитывать число двоичных наборов, удовлетворяющих заданным условиям. Самое сложное, т.к. нет формальных правил, как это сделать, требуется догадка.

Без чего не обойтись!

Без чего не обойтись!

Условные обозначения конъюнкция: A /\ B , A  B , AB , А &B, A and B дизъюнкция: A \ / B , A + B , A | B , А or B отрицание:  A , А, not A эквиваленция: A  В, A  B, A  B исключающее «или»: A  B , A xor B

Метод замены переменных Сколько существует различных наборов значений логических переменных х1, х2, …, х9, х10, которые удовлетворяют всем перечисленным ниже условиям: ((x1 ≡ x2) \/ (x3 ≡ x4)) /\ (¬(x1 ≡ x2) \/ ¬(x3 ≡ x4)) = 1 ((x3 ≡ x4) \/ (x5 ≡ x6)) /\ (¬(x3 ≡ x4) \/ ¬(x5 ≡ x6)) = 1 ((x5 ≡ x6) \/ (x7 ≡ x8)) /\ (¬(x5 ≡ x7) \/ ¬(x7 ≡ x8)) = 1 ((x7 ≡ x8) \/ (x9 ≡ x10)) /\ (¬(x7 ≡ x8) \/ ¬(x9 ≡ x10)) = 1 В ответе не нужно перечислять все различные наборы х1, х2, …, х9, х10, при которых выполняется данная система равенств. В качестве ответа необходимо указать количество таких наборов (демо-версия 2012 г.)

Решение Шаг 1. Упрощаем, выполнив замену переменных t1 = x1  x2 t2 = x3  x4 t3 = x5  x6 t4 = x7  x8 t5 = x9  x10 После упрощения: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) =1 (t2 \/ t3) /\ (¬t2 \/ ¬ t3) =1 (t3 \/ t4) /\ (¬t3 \/ ¬ t4) =1 (t4 \/ t5) /\ (¬t4 \/ ¬ t5) =1 Рассмотрим одно из уравнений: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) =1 Очевидно, оно =1 только если одна из переменных равна 0, а другая – 1. Воспользуемся формулой для выражения операции XOR через конъюнкцию и дизъюнкцию: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) = t1  t2 = ¬(t1 ≡ t2) =1 ¬(t1 ≡ t2) =1 ¬(t2 ≡ t3) =1 ¬(t3 ≡ t4) =1 ¬(t4 ≡ t5) =1

Шаг2. Анализ системы ¬(t1 ≡ t2) =1 ¬(t2 ≡ t3) =1 ¬(t3 ≡ t4) =1 ¬(t4 ≡ t5) =1 t1 t2 t3 t4 t5 0 1 0 1 0 1 0 1 0 1 Т.к. tk = x2k-1 ≡ x2k (t1 = x1  x2 ,….), то каждому значению tk соответствует две пары значений x2k-1 и x2k , например: tk =0 соответствуют две пары - (0,1) и (1,0) , а tk =1 – пары (0,0) и (1,1).

Шаг3. Подсчет числа решений. Каждое t имеет 2 решения, количество t – 5. Т.о. для переменных t существует 2 5 = 32 решения. Но каждому t соответствует пара решений х, т.е. исходная система имеет 2*32 = 64 решения. Ответ: 64

Метод исключения части решений Сколько существует различных наборов значений логических переменных х1, х2, …, х5, y1,y2,… , y5 , которые удовлетворяют всем перечисленным ниже условиям: (x1→ x2)∧(x2→ x3)∧(x3→ x4)∧(x4→ x5) =1; (y1→ y2)∧(y2→ y3)∧(y3→ y4) ∧(y4→ y5) =1; y5→ x5 =1. В ответе не нужно перечислять все различные наборы х1, х2, …, х5, y 1 ,y2,… , y5, при которых выполняется данная система равенств. В качестве ответа необходимо указать количество таких наборов.

Решение. Шаг1. Последовательное решение уравнений х1 1 0 х2 1 0 1 х3 1 0 1 1 х4 1 0 1 1 1 х5 1 0 1 1 1 1 Первое уравнение – конъюнкция нескольких операций импликации, равна 1, т.е. каждая из импликаций истинна. Импликация ложна только в одном случае, когда 1  0, во всех других случаях (0  0, 0  1, 1  1) операция возвращает 1. Запишем это в виде таблицы:

Шаг1. Последовательное решение уравнений Т.о. получено 6 наборов решений для х1,х2,х3,х4,х5: (00000), (00001), (00011), (00111), (01111), (11111). Рассуждая аналогично, приходим к выводу, что для y1, y2, y3, y4, y5 существует такой же набор решений. Т.к. уравнения эти независимы, т.е. в них нет общих переменных, то решением этой системы уравнений (без учета третьего уравнения) будет 6*6= 36 пар «иксов» и «игреков». Рассмотрим третье уравнение: y5→ x5 =1 Решением являются пары: 0 0 0 1 1 1 Не является решением пара: 1 0

Сопоставим полученные решения Там, где y5 =1, не подходят x5=0. таких пар 5. Количество решений системы: 36-5= 31 . Ответ: 31 Понадобилась комбинаторика!!!

Метод динамического программирования Сколько различных решений имеет логическое уравнение x 1 → x 2 → x 3 → x 4 → x 5 → x 6 = 1, где x 1, x 2, …, x 6 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количеств о таких наборов.

Решение Шаг1. Анализ условия Слева в уравнении последовательно записаны операции импликации, приоритет одинаков. Перепишем: ((((X 1 → X 2) → X 3) → X 4) → X 5) → X 6 = 1 NB! Каждая следующая переменная зависит не от предыдущей, а от результата предыдущей импликации!

Шаг2. Выявление закономерности Рассмотрим первую импликацию, X 1 → X 2. Таблица истинности: X 1 X 2 X 1 → X 2 0 0 1 0 1 1 1 0 0 1 1 1 Из одного 0 получили 2 единицы, а из 1 получили один 0 и одну 1. Всего один 0 и три 1, это результат первой операции.

Шаг2. Выявление закономерности Подключив к результату первой операции x 3 , получим: F(x 1 ,x 2) x 3 F(x 1 ,x 2)  x 3 0 0 1 0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 Из двух 0 – две 1, из каждой 1 (их 3) по одному 0 и 1 (3+3)

Шаг 3. Вывод формулы Т.о. можно составить формулы для вычисления количества нулей N i и количества единиц E i для уравнения с i переменными: ,

Шаг 4. Заполнение таблицы Заполним слева направо таблицу для i = 6, вычисляя число нулей и единиц по приведенным выше формулам; в таблице показано, как строится следующий столбец по предыдущему: : число переменных 1 2 3 4 5 6 Число нулей N i 1 1 3 5 11 21 Число единиц E i 1 2*1+1= 3 2*1+3= 5 11 21 43 Ответ: 43

Метод с использованием упрощений логических выражений Сколько различных решений имеет уравнение ((J → K) → (M  N  L))  ((M  N  L) → (¬ J  K))  (M → J) = 1 где J , K, L, M, N – логические переменные? В ответе не нужно перечислять все различные наборы значений J , K, L, M и N, при которых выполнено данное равенство. В качестве ответа Вам нужно указать количество таких наборов.

Решение Заметим, что J → K = ¬ J  K Введем замену переменных: J → K=А, M  N  L =В Перепишем уравнение с учетом замены: (A → B)  (B → A)  (M → J)=1 4. (A  B)  (M → J)= 1 5. Очевидно, что A  B при одинаковых значениях А и В 6. Рассмотрим последнюю импликацию M → J =1 Это возможно, если: M=J=0 M=0, J=1 M=J=1

Решение Т.к. A  B , то При M=J=0 получаем 1 + К=0. Нет решений. При M=0, J=1 получаем 0 + К=0, К=0, а N и L - любые, 4 решения: ¬ J  K = M  N  L K N L 0 0 0 0 0 1 0 1 0 0 1 1

Решение 10. При M=J=1 получаем 0+К=1 *N * L , или K=N*L, 4 решения: 11. Итого имеет 4+4=8 решений Ответ: 8 K N L 0 0 0 0 0 1 0 1 0 1 1 1

Источники информации: О.Б. Богомолова, Д.Ю. Усенков. В15: новые задачи и новое решение // Информатика, № 6, 2012, с. 35 – 39. К.Ю. Поляков. Логические уравнения // Информатика, № 14, 2011, с. 30-35. http://ege-go.ru/zadania/grb/b15/ , [ Электронный ресурс ] . http://kpolyakov.narod.ru/school/ege.htm , [ Электронный ресурс ] .

Назначение сервиса . Онлайн-калькулятор предназначен для построения таблицы истинности для логического выражения .
Таблица истинности – таблица содержащая все возможные комбинации входных переменных и соответствующее им значения на выходе.
Таблица истинности содержит 2 n строк, где n – число входных переменных, и n+m – столбцы, где m – выходные переменные.

Инструкция . При вводе с клавиатуры используйте следующие обозначения:

Логическое выражение :

Вывод промежуточных таблиц для таблицы истинности
Построение СКНФ
Построение СДНФ
Построение полинома Жегалкина
Построение карты Вейча-Карно
Минимизация булевой функции

Например, логическое выражение abc+ab~c+a~bc необходимо ввести так: a*b*c+a*b=c+a=b*c
Для ввода данных в виде логической схемы используйте этот сервис .

Правила ввода логической функции

1. Вместо символа v (дизъюнкция, ИЛИ) используйте знак + .
2. Перед логической функцией не надо указывать обозначение функции. Например, вместо F(x,y)=(x|y)=(x^y) необходимо ввести просто (x|y)=(x^y) .
3. Максимальное количество переменных равно 10 .

Проектирование и анализ логических схем ЭВМ ведётся с помощью специального раздела математики - алгебры логики. В алгебре логики можно выделить три основные логические функции: "НЕ" (отрицание), "И" (конъюнкция), "ИЛИ" (дизъюнкция).
Для создания любого логического устройства необходимо определить зависимость каждой из выходных переменных от действующих входных переменных такая зависимость называется переключательной функцией или функцией алгебры логики.
Функция алгебры логики называется полностью определённой если заданы все 2 n её значения, где n – число выходных переменных.
Если определены не все значения, функция называется частично определённой.
Устройство называется логическим, если его состояние описывается с помощью функции алгебры логики.
Для представления функции алгебры логики используется следующие способы:
По алгебраической форме можно построить схему логического устройства, используя логические элементы.


Рисунок1- Схема логического устройства

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

Операция НЕ - логическое отрицание (инверсия)

Логическая операция НЕ применяется к одному аргументу, в качестве которого может быть и простое, и сложное логическое выражение. Результатом операции НЕ является следующее:

• если исходное выражение истинно, то результат его отрицания будет ложным;
• если исходное выражение ложно, то результат его отрицания будет истинным.

Для операции отрицания НЕ приняты следующие условные обозначения:
не А, Ā, not A, ¬А, !A
Результат операции отрицания НЕ определяется следующей таблицей истинности:

A	не А
0	1
1	0

Результат операции отрицания истинен, когда исходное высказывание ложно, и наоборот.

Операция ИЛИ - логическое сложение (дизъюнкция, объединение)

Логическая операция ИЛИ выполняет функцию объединения двух высказываний, в качестве которых может быть и простое, и сложное логическое выражение. Высказывания, являющиеся исходными для логической операции, называют аргументами. Результатом операции ИЛИ является выражение, которое будет истинным тогда и только тогда, когда истинно будет хотя бы одно из исходных выражений.
Применяемые обозначения: А или В, А V В, A or B, A||B.
Результат операции ИЛИ определяется следующей таблицей истинности:
Результат операции ИЛИ истинен, когда истинно А, либо истинно В, либо истинно и А и В одновременно, и ложен тогда, когда аргументы А и В - ложны.

Операция И - логическое умножение (конъюнкция)

Логическая операция И выполняет функцию пересечения двух высказываний (аргументов), в качестве которых может быть и простое, и сложное логическое выражение. Результатом операции И является выражение, которое будет истинным тогда и только тогда, когда истинны оба исходных выражения.
Применяемые обозначения: А и В, А Λ В, A & B, A and B.
Результат операции И определяется следующей таблицей истинности:

A	B	А и B
0	0	0
0	1	0
1	0	0
1	1	1

Результат операции И истинен тогда и только тогда, когда истинны одновременно высказывания А и В, и ложен во всех остальных случаях.

Операция «ЕСЛИ-ТО» - логическое следование (импликация)

Эта операция связывает два простых логических выражения, из которых первое является условием, а второе - следствием из этого условия.
Применяемые обозначения:
если А, то В; А влечет В; if A then В; А→ В.
Таблица истинности:

A	B	А → B
0	0	1
0	1	1
1	0	0
1	1	1

Результат операции следования (импликации) ложен только тогда, когда предпосылка А истинна, а заключение В (следствие) ложно.

Операция «А тогда и только тогда, когда В» (эквивалентность, равнозначность)

Применяемое обозначение: А ↔ В, А ~ В.
Таблица истинности:

A	B	А↔B
0	0	1
0	1	0
1	0	0
1	1	1

Операция «Сложение по модулю 2» (XOR, исключающее или, строгая дизъюнкция)

Применяемое обозначение: А XOR В, А ⊕ В.
Таблица истинности:

A	B	А⊕B
0	0	0
0	1	1
1	0	1
1	1	0

Результат операции эквивалентность истинен только тогда, когда А и В одновременно истинны или одновременно ложны.

Приоритет логических операций

• Действия в скобках
• Инверсия
• Конъюнкция (&)
• Дизъюнкция (V), Исключающее ИЛИ (XOR), сумма по модулю 2
• Импликация (→)
• Эквивалентность (↔)

Совершенная дизъюнктивная нормальная форма

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

1. Каждое логическое слагаемое формулы содержит все переменные, входящие в функцию F(x 1 ,x 2 ,...x n).
2. Все логические слагаемые формулы различны.
3. Ни одно логическое слагаемое не содержит переменную и её отрицание.
4. Ни одно логическое слагаемое формулы не содержит одну и ту же переменную дважды.

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

Совершенная конъюнктивная нормальная форма

Совершенная конъюнктивная нормальная форма формулы (СКНФ) это равносильная ей формула, представляющая собой конъюнкцию элементарных дизъюнкций, удовлетворяющая свойствам:

1. Все элементарные дизъюнкции содержат все переменные, входящие в функцию F(x 1 ,x 2 ,...x n).
2. Все элементарные дизъюнкции различны.
3. Каждая элементарная дизъюнкция содержит переменную один раз.
4. Ни одна элементарная дизъюнкция не содержит переменную и её отрицание.