Данная методика основана на использование таблиц истинности, рассчитана на учащихся, которые владеют методами преобразования логических выражений. Если учащиеся плохо владеют этими методами, можно использовать и без преобразований. (Мы будем использовать преобразования). Для овладения этим способом решения, необходимы в обязательном порядке знание свойств основных логических операций: конъюнкции, дизъюнкции, инверсии, импликации и эквивалентности.
Алгоритм решения систем уравнений по этому методу:
Преобразовать логическое уравнение, упростить его.
Определить последовательность решения уравнений в системе, так как в большинстве случаев идет последовательное решение уравнений сверху вниз (как они расположены в системе), но есть варианты, когда удобнее, проще начать решать снизу вверх.
Построить таблицу переменных, где задать начальные значения первой переменной (или последней).
Последовательно прописать возможные варианты следующей переменной при каждом значении первой.
После решения предыдущего уравнения, переходя на следующее, обязательно обращать внимание: какие переменные используются в предыдущем и последующем уравнении, так как полученные при решении в предыдущих уравнениях значения переменных переходят как варианты для следующих уравнений.
Обращать внимание на получаемые количества решения при переходе к следующей переменной, т.к. может быть выявлена закономерность в увеличении решений.
Пример1.
¬ X 1 ˅ X 2=1
¬ X 2 ˅ X 3=1
¬ X 3 ˅ X 4=1
¬ X 9 ˅ X 10=1
Начнем с Х1 и посмотрим какие значения эта переменная может принимать: 0 и 1.
Затем рассмотрим каждое из этих значений и посмотрим, какое может быть при этом Х2.
Ответ: 11 решений
Пример 2.
( X 1˄ X 2)˅(¬ X 1˄¬ X 2) ˅( X 1↔ X 3)=1
( X 2˄ X 3)˅(¬ X 2˄¬ X 3) ˅( X 2↔ X 4)=1
(X8˄ X9)˅(¬X8˄¬X9) ˅(X8↔X10)=0
Преобразуем по формуле (A ˄ B )˅ (¬ A ˄ ¬ B )= A ↔ B
Получаем:
( X 1↔ X 2) ˅ ( X 1↔ X 3) =1
( X 2↔ X 3) ˅ ( X 2↔ X 4) =1
( X 8↔ X 9) ˅ ( X 8↔ X 10) =0
Для Х1 =0 - 8 решений
Возьмем Х1=1 и посмотрим какие значение может принимать Х2. Теперь для каждого Х2 рассмотрим какие значения может принимать Х3 и т.д.
Для Х1=1 – 8 решений
Итого 8+8=16 решений
Ответ. 16 решений
Пример 3 .
¬ ( X 1↔ X 2) ˄ ( X 1 ˅ X 3) ˄ (¬ X 1 ˅ ¬ X 3 )=0
¬ ( X 2↔ X 3) ˄ ( X 2 ˅ X 4) ˄ (¬ X 2 ˅ ¬ X 4)=0
….
¬ ( X 8↔ X 9) ˄ ( X 8 ˅ X 10) ˄ (¬ X 8 ˅ ¬ X 10)=0
После преобразований (A ˅ B ) ˄(¬ A ˅¬ B )= ¬( A ↔ B )
получаем:
¬ ( X 1↔ X 2) ˄ ¬ ( X 1↔ X 3)=0
¬ ( X 2↔ X 3) ˄ ¬ ( X 2↔ X 4)=0
…..
¬ ( X 8↔ X 9) ˄ ¬ ( X 8↔ X 10)=0
Возьмем Х1=0 и посмотрим какие значение может принимать Х2. Теперь для каждого Х2 рассмотрим какие значения может принимать Х3 и т.д
Получилось 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 )= A ↔ B . Получим:
(Х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, а следующие переменные могут принимать разные значения. Будем рассматривать каждое .
Итого 21 решение для Х10=0
Теперь рассмотрим для Х10=1. Получаем тоже 21 решение
Итого:21+21=42
Ответ: 42 решения
Пример 5.
( X 1 ˄ X 2) ˅ (¬ X 1 ˄ ¬ X 2) ˅ (¬ X 3 ˄ X 4) ˅ ( X 3 ˄ ¬ X 4)=1
( X 3 ˄ X 4) ˅ (¬ X 3 ˄ ¬ X 4) ˅ (¬ X 5 ˄ X 6) ˅ ( X 5 ˄ ¬ X 6)=1
( X 5 ˄ X 6) ˅ (¬ X 5 ˄ ¬ X 6) ˅ (¬ X 7 ˄ X 8) ˅ ( X 7 ˄ ¬ X 8)=1
( X 7 ˄ X 8) ˅ (¬ X 7 ˄ ¬ X 8) ˅ (¬ X 9 ˄ X 10) ˅ ( X 9˄ ¬ X 10) =1
Преобразуем по формулам: (¬ A ˄ B ) ˅ ( A ˄ ¬ B )= A ↔ ¬ B
( A ˄ B )˅ (¬ A ˄ ¬ B )= A ↔ B
( X 1↔ X 2) ˅ ( X 3 ↔ ¬ X 4)=1
( X 3↔ X 4) ˅ ( X 5 ↔ ¬ X 6)=1
( X 5↔ X 6) ˅ ( X 7 ↔ ¬ X 8)=1
( X 7↔ X 8) ˅ ( X 9 ↔ ¬ X 10)=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 решения.
Итого: 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 и т.д.
Видим некоторую закономерность: Количество следующих решений равно сумме двух предыдущих.
То же самое для Х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
Введем замену:
T 1 =(Х1↔ Х2)
T 2 =(Х2↔ Х3)
T 3 =(Х3↔ Х4)
T 4 =(Х4↔ Х5)
T 5 =(Х5↔ Х6)
T 6 =(Х6↔ Х7)
T 7 =(Х7↔ Х8)
T 8 =(Х8↔ Х9)
T 9 =(Х9↔ Х10)
Получаем:
T 1 ˅ T 2=1
T 2 ˅ T 3=1
T 3 ˅ T 4=1
T 4 ˅ T 5=1
T 5 ˅ T 6=1
T 6 ˅ T 7=1
T 7 ˅ T 8=1
T 8 ˅ T 9=1
T 9 ˅ T 10=1
Возьмем T 1=1 и используем свойства дизъюнкции:
НО Вспомним, что
T 1 =(Х1↔ Х2)
T 2 =(Х2↔ Х3) и т.д.
Воспользуемся свойством эквивалентности и убедимся, глядя на таблицу, что
Когда Т =1, то получается два решения. А когда =0 –одно решение.
Следовательно, можно подсчитать количество единиц и умножить их на 2+ количество нулей. Подсчет, так же используя закономерность .
Получается, что количество единиц = предыдущему общему количеству решений Т, а количество нулей равно предыдущему количеству единиц
Итак. Получим. Так как единица дает два решения, то 34*2=68 решений из единицы+21 решение из 0.
Итого 89 решений для Т=1. Аналогичным способом получаем 89 решений для Т=0
Итого 89+89=178
Ответ: 178 решений
Пример 7.
(X 1 ↔ X 2) ˅ (X 3↔ X 4) ˄ ¬(X 1 ↔ X 2) ˅ ¬(X 3↔ X 4)=1
(X 3 ↔ X 4) ˅ (X 5↔ X 6) ˄ ¬(X 3 ↔ X 4) ˅ ¬(X 5↔ X 6)=1
(X 5 ↔ X 6) ˅ (X 7↔ X 8) ˄ ¬(X 5 ↔ X 6) ˅ ¬(X 7↔ X 8)=1
(X 7 ↔ X 8) ˅ (X 9↔ X 10) ˄ ¬(X 7 ↔ X 8) ˅ ¬(X 9↔ X 10)=1
Введем замену:
T 1=(X 1 ↔ X 2)
T 2=(X 3↔ X 4)
T 3=(X 5↔ X 6)
T 4=(X 7 ↔ X 8)
T 5=(X 9↔ X 10)
Получим:
(Т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
Получаем: 2 5 =32 для Т
Итого: 32+32=64
Ответ: 64 решения.
Тема урока: Решение логических уравнений
Образовательная – изучение способов решения логических уравнений, формирование умений и навыков решения логических уравнений и построения логического выражения по таблице истинности;Развивающая - создать условия для развития познавательного интереса учащихся, способствовать развитию памяти, внимания, логического мышления;
Воспитательная : способствовать воспитанию умения выслушивать мнение других, воспитание воли и настойчивости для достижения конечных результатов.
Тип урока: комбинированный урок
Оборудование: компьютер, мультимедийный проектор, презентация 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 минут)
Решить уравнение:
Сколько решений имеет уравнение (в ответе укажите только число)?
По заданной таблице истинности составить логическое выражение и
упростить его.
Пусть – логическая функция от n переменных. Логическое уравнение имеет вид:
Константа С имеет значение 1 или 0.
Логическое уравнение может иметь от 0 до различных решений. Если С равно 1, то решениями являются все те наборы переменных из таблицы истинности, на которых функция F принимает значение истина (1). Оставшиеся наборы являются решениями уравнения при C, равном нулю. Можно всегда рассматривать только уравнения вида:
Действительно, пусть задано уравнение:
В этом случае можно перейти к эквивалентному уравнению:
Рассмотрим систему из k логических уравнений:
Решением системы является набор переменных, на котором выполняются все уравнения системы. В терминах логических функций для получения решения системы логических уравнений следует найти набор, на котором истинна логическая функция Ф, представляющая конъюнкцию исходных функций :
Если число переменных невелико, например, менее 5, то нетрудно построить таблицу истинности для функции , что позволяет сказать, сколько решений имеет система и каковы наборы, дающие решения.
В некоторых задачах ЕГЭ по нахождению решений системы логических уравнений число переменных доходит до значения 10. Тогда построить таблицу истинности становится практически неразрешимой задачей. Для решения задачи требуется другой подход. Для произвольной системы уравнений не существует общего способа, отличного от перебора, позволяющего решать такие задачи.
В предлагаемых на экзамене задачах решение обычно основано на учете специфики системы уравнений. Повторяю, кроме перебора всех вариантов набора переменных, общего способа решения задачи нет. Решение нужно строить исходя из специфики системы. Часто полезно провести предварительное упрощение системы уравнений, используя известные законы логики. Другой полезный прием решения этой задачи состоит в следующем. Нам интересны не все наборы, а только те, на которых функция имеет значение 1. Вместо построения полной таблицы истинности будем строить ее аналог - бинарное дерево решений. Каждая ветвь этого дерева соответствует одному решению и задает набор, на котором функция имеет значение 1. Число ветвей в дереве решений совпадает с числом решений системы уравнений.
Что такое бинарное дерево решений и как оно строится, поясню на примерах нескольких задач.
Задача 18
Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, которые удовлетворяют системе из двух уравнений?
Ответ: Система имеет 36 различных решений.
Решение: Система уравнений включает два уравнения. Найдем число решений для первого уравнения, зависящего от 5 переменных – . Первое уравнение можно в свою очередь рассматривать как систему из 5 уравнений. Как было показано, система уравнений фактически представляет конъюнкцию логических функций. Справедливо и обратное утверждение, - конъюнкцию условий можно рассматривать как систему уравнений.
Построим дерево решений для импликации () - первого члена конъюнкции, который можно рассматривать как первое уравнение. Вот как выглядит графическое изображение этого дерева
Дерево состоит из двух уровней по числу переменных уравнения. Первый уровень описывает первую переменную . Две ветви этого уровня отражают возможные значения этой переменной – 1 и 0. На втором уровне ветви дерева отражают только те возможные значения переменной , для которых уравнение принимает значение истина. Поскольку уравнение задает импликацию, то ветвь, на которой имеет значение 1, требует, чтобы на этой ветви имело значение 1. Ветвь, на которой имеет значение 0, порождает две ветви со значениями , равными 0 и 1. Построенное дерево задает три решения, на которых импликация принимает значение 1. На каждой ветви выписан соответствующий набор значений переменных, дающий решение уравнения.
Вот эти наборы: {(1, 1), (0, 1), (0, 0)}
Продолжим построение дерева решений, добавляя следующее уравнение, следующую импликацию . Специфика нашей системы уравнений в том, что каждое новое уравнение системы использует одну переменную из предыдущего уравнения, добавляя одну новую переменную. Поскольку переменная уже имеет значения на дереве, то на всех ветвях, где переменная имеет значение 1, переменная также будет иметь значение 1. Для таких ветвей построение дерева продолжается на следующий уровень, но новые ветви не появляются. Единственная ветвь, где переменная имеет значение 0, даст разветвление на две ветви, где переменная получит значения 0 и 1. Таким образом, каждое добавление нового уравнения, учитывая его специфику, добавляет одно решение. Исходное первое уравнение:
имеет 6 решений. Вот как выглядит полное дерево решений для этого уравнения:
Второе уравнение нашей системы аналогично первому:
Разница лишь в том, что в уравнении используются переменные Y. Это уравнение также имеет 6 решений. Поскольку каждое решение для переменных может быть скомбинировано с каждым решением для переменных , то общее число решений равно 36.
Заметьте, построенное дерево решений дает не только число решений (по числу ветвей), но и сами решения, выписанные на каждой ветви дерева.
Задача 19
Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, которые удовлетворяют всем перечисленным ниже условиям?
Эта задача является модификацией предыдущей задачи. Разница в том, что добавляется еще одно уравнение, связывающее переменные X и Y.
Из уравнения следует, что когда имеет значение 1(одно такое решение существует), то и имеет значение 1. Таким образом, существует один набор, на котором и имеют значения 1. При , равном 0, может иметь любое значение, как 0, так и 1. Поэтому каждому набору с , равном 0, а таких наборов 5, соответствует все 6 наборов с переменными Y. Следовательно, общее число решений равно 31.
Задача 20
Решение: Вспоминания основные эквивалентности, запишем наше уравнение в виде:
Циклическая цепочка импликаций означает тождественность переменных, так что наше уравнение эквивалентно уравнению:
Это уравнение имеет два решения, когда все равны либо 1, либо 0.
Задача 21
Сколько решений имеет уравнение:
Решение: Так же, как и в задаче 20, от циклических импликаций перейдем к тождествам, переписав уравнение в виде:
Построим дерево решений для этого уравнения:
Задача 22
Сколько решений имеет следующая система уравнений?
УДК 004.023
Семенов Сергей Максимович
Владивостокский государственный университет экономики и сервиса Россия. Владивосток
Об одном способе решения систем логических уравнений
Рассматривается способ определения количества решений системы логических уравнений. Способ основан на построении дерева решений и определении рекуррентных соотношений для уровня N. Применение разработанного способа обеспечивает конструктивный подход к решению задачи В15 ЕГЭ.
Ключевые слова и словосочетания: системы логических уравнений, дерево решений, рекуррентные соотношения, B15, ЕГЭ.
На практике системы логических уравнений полезны при разработке цифровых логических устройств . Решению систем логических уравнений посвящена одна из задач ЕГЭ по информатике. К сожалению, различные известные способы решения этой задачи не позволяют сформировать какой-то один подход к решению этой задачи. В результате решение задачи вызывает большие затруднения у выпускников. Мы предлагаем способ решения систем логических уравнений, который позволяет выпускнику следовать вполне определенному алгоритму. Идея этого способа изложена в . Мы применили и развили данную идею (построение дерева решений), почти не используя таблицы истинности для всего дерева. При решении различных задач выяснилось, что количество решений многих систем логических уравнений подчиняется рекуррентным соотношениям, таким, как числа Фибоначчи и др.
Системы логических уравнений. Будем придерживаться следующих обозначений: дизъюнкция (+), конъюнкция ( ), исключающее ИЛИ (©), импликация (->■), эквивалентность (=), отрицание (-■). На рисунках темный кружок обозначает 1, а светлый кружок - 0. Fl - количество решений при Х1, равном 1. Fo - количество решений при Х1, равном 0. N - число переменных в системе уравнений. F(N) = F1(N) + F0(N) - общее число решений.
Задание 1. Нужно найти количество решений системы уравнений (, тест № 2)
Вначале полагаем Х1 = 1. Тогда для первого уравнения значения Х2 и Хз могут быть любыми. Таким образом, дерево построено до третьего уровня. Далее с учетом Х2 и Хз выбираем Х4. После этого алгоритм повторяется для каждой тройки переменных (рис. 1). Начиная с четвертого уровня можно заметить, что Fl(4)=Fl(3)+Fl(1), Fl(5)=Fl(4)+Fl(2). Таким образом, получаем Fl(N) = Fl(N-1) + Fl(N-3) (1)
Рис. 1. Задание 1
Из уравнения (1) следует:
Бх(8) = 16 + 7 = 23,
Fl(9) = 23 + 11 = 34.
Чтобы построить дерево из нуля, можно воспользоваться нижней ветвью из рис. 1. Легко видеть, что она повторяет основное дерево, но со сдвигом вправо на 2, то есть
Итого, F(9) = Fl(9) + Fo(9) = 34 + 16 = 50.
При построении дерева решений можно визуально установить рекуррентные соотношения для определения количества решений на уровне N.
Принцип математической индукции гласит: пусть имеется последовательность утверждений Fl, F2, Fз и пусть первое утверждение Fl верно. Мы можем доказать, что из верности утверждения FN следует верность FN+l. Тогда все утверждения в этой последовательности верны.
Рассмотрим рис. 2 для задания 1.
к2 >3 х5 хб Х7
Рис. 2. Анализ дерева решений
На рисунке 2 выделены фигуры, имеющие общую вершину (комбинации значений переменных) для первых пяти уравнений системы. В каждом уравнении задействованы три переменных, поэтому фигуры составляются из значений трех переменных (трех уровней дерева). Для того чтобы идентифицировать фигуры, можно было бы ввести обозначения. Однако мы поступим следующим образом: каждой фигуре поставим в соответствие количество составляющих ее кружков (значений переменных). Тогда получим для последовательности следующие уравнения:
4. 7, 4, 4, 1, 7
5. 7, 4, 4, 1, 7, 7, 4.
С уравнения 4 можно видеть, что фигуры для уравнения N состоят из фигур уравнения N-1 и фигур уравнения N-3. Важно, что других фигур нет и быть не может для данного типа уравнений, то есть переход от одного уравнения к другому производится путем увеличения числа фигур из ограниченного набора по строго определенным правилам. Этот факт и является основным для того, чтобы утверждать по индукции, что для уравнения N+1 набор фигур будет состоять из фигур уравнения N и фигур уравнения N-2.
Другим способом идентификации фигур является определение количества значений переменных на последнем уровне для данного уравнения, то есть нужно перейти от номера уравнения к номеру уровня дерева, поскольку нам нужно определить количество решений для системы уравнений, Тогда для построенного дерева получим последовательность: 1, 2, 4, 5, 7, 11, 16. Для этой последовательности справедлива формула: FN = FN-1 + FN-3.
В соответствии с нашими рассуждениями эта формула будет верна для N+1, а по индукции и для любого N.
Приведенный способ доказательства можно использовать для любых систем подобного типа. На практике достаточно определять рекуррентное соотношение для уровня N поскольку в основе его лежит ограниченный набор фигур и способов их преобразований при переходе от уравнения, соответствующего уровню N к уравнению, соответствующему уровню N+1.
Задание 2. Нужно найти количество решений системы уравнений (, 4.16)
(Х1=Х2) + (Х1 = Х3) = 1 (Х2=Хз) + (Х2 = Х4) = 1 (Хз=Х4) + (Хз = Х5) = 1 (Х4=Х5) + (Х4 = Х6)=1 (Х5 = Х6) + (Х5 = Х7) = 1
XI Х2 ХЗ >:1 Х5 Хб Х7
Рис. 3. Задание 2
Для получения числа решений задания 2 можно было не строить дерево решений полностью (рис. 3), так как очевидно, что Fl(N) = N. Аналогично, Fo(N) = N. Итого F(7) = 7 + 7 = 14.
Задание 3. Нужно найти количество решений системы уравнений (, тест № 1)
(Х1 ^ Х2) ■ (Х2 ^ Хз) ■ (Хз ^ Х4) ■ (Х4 ^ Х5) = 1
(Yl ^ Y2) ■ (У2 ^ Yз) ■ (Yз ^ Y4) ■ (Y4 ^ Y5) = 1
(Yl ^ Х1) ■ (У2 ^ Х2) ■ (Yз ^ Хз) ■ (У4 ^ Х4) ■ (Y5 ^ Х5) = 1
На рисунке 4 показаны деревья решений для X и Y и приведены соответствующие таблицы истинности.
Рис. 4. Задание 3
Из первых двух уравнений, поскольку X и Y независимы, следует, что общее число решений F(5) = 6 * 6 = 36. Для того чтобы учесть третье уравнение, нужно для каждой переменной Y подсчитать, какое число наборов из таблицы X не удовлетворяет уравнению. Импликация Yi ^ Xi = 0, если Yi = 1, а Xi = 0. Иначе говоря, для Yl = 1 третьему уравнению не удовлетворяют все строки из таблицы X, где Х1 = 0. Число таких строк равно 5. Для Y2 = 1 таких строк - 4 и т.д. Общее число строк, которые не удовлетворяют третьему уравнению, равно 5 + 4 + 3 + 2 + 1 = 15.
Таким образом, общее число допустимых решений равно 36 - 15 = 21. Задание 4. Нужно найти количество решений системы уравнений (, 4.17.а)
(Х1=Х2) + (Х1 = Х3) = (Х2 = Х3) + (Х2 = Х4) = (Х4=Х5) + (Х4 = Х6) = (Х5 = Х6) + (Х5 = Х7) = (Хб=Х7) + (Хб = Х8) = (Х5=Х6) = 0
Рис. 5. Задание 4
Для данного примера сложно определить конечную формулу F(N), проще построить дерево решений до конца (или хотя бы до Х6). На рисунке 5 показано построенное дерево решений. В результате получаем F(8) = Fl(8) + Fo(8) = 5 + 5 = 10.
Задание 5. Необходимо найти количество решений системы уравнений (, 4.17.б)
(Х1=Х2) + (Х1 = Х3) = 1 (Х2=Х3) + (Х2 = Х4) = 1 (Х3 = Х4) + (Х3 = Х5) = 1 (Х4=Х5) + (Х4 = Х6)=1 (Х5 = Х6) + (Х5 = Х7) = 1 (Х6 = Х8) = 1
Для этого примера, так же как и для предыдущего, проще построить дерево решений до конца (рис. 6). В результате получаем F(8) = Fl(8) + Fo(8) = 7 + 7 = 14.
Задание 6. Нужно найти количество решений системы уравнений ([!]> 4.17.в)
(Х!8"Х2) + (Х2ЕХз) = 1 (Х2фХз) + (Хз = Х4) = 1 (Хз8"Х4) + (Х4 = Х5) = 1 (Х4©Х5) + (Х5 = Хб) = 1 (Х5фХб) + (Хб = Х7) = 1 (Хб©Х7) + (Х7 = Х8) = 1 Дерево решений показано на рис. 7.
XI Х2 ХЗ Х4 Х5 Х6 Х7 Х8 XI Х2 ХЗ Х4 Х5 Х6 Х7 Х8
Рис. 6. Задание 5 Рис. 7. Задание 6
Для данной системы уравнений можно было не строить полное дерево решений, так как уже с третьего - четвертого шага понятно, что F1(N) = N. Легко увидеть, что Fo(N) можно получить из дерева, начинающегося на втором уровне из нуля. Тогда Fo(N) = N. Итого, F(8) = Fl(8) + Fo(8) = 8 + 8 = 16.
Задание 7. Нужно найти количество решений системы уравнений
(Х4ЭХ5) + (Х4 ©Х6) = 1 (Х5©Хб) + (Х5©Х7) = 1
Заметим, что если X! = X2 = 1, то первое уравнение выполняется при Xз = 0. Построим сначала дерево для Xl = X2 = 1 (рис. 8). Тогда число решений Fl(N) = Fll(N) + Flo(N).
XI Х2 ХЗ Х4 Х5 Х6 Х7 Х8
Рис. 8. Задание 7
Из рисунка 8 видно, что число решений F11(N) = F11(N-1) + F11(N-2). Иначе говоря, число решений описывается числами Фибоначчи. Вторую ветку дерева для F10 можно не строить, так как она получается из рис. 1, начиная со второго уровня. Тогда F10(N) = F11(N+1). Окончательно получаем, что Fll(8) = 1з и Flo(8) = Fll(9) = 1з + 8 = 21. Тогда Fl(8) = Fll(8) + Flo(8) = 1з + 21 = з4.
Для того чтобы получить F0(N), также необязательно строить дерево решений, поскольку оно получается из рис. 1 начиная с третьего уровня. Тогда Fo(N) = Fll(N+2). Отсюда получаем, что Fo(8) = Fll(10) = Fll(9) + Fll(8) = 21 + 1з = з4. Таким образом, общее число решений F(8)= F1(8) + F0(8) = з4 + з4 = 68.
Задание 8. Нужно найти количество решений системы уравнений ([з], Задание 2)
(Х1 + Х2) ^ (Хз + Х4) = 1 (Хз + Х4) ^ (Х5 + Х6) = 1 (Х5 + Х6) ^ (Х7 + Х8) = 1 (Х7 + Х8) ^ (Х9 + Х10) = 1
Сделаем подстановку (Х1 + Х2) = Yl и т.д. и получим систему уравнений:
^ ^ Y2 = 1 Y2 ^ Yз = 1 Yз ^ Y4 = 1 Y4 ^ Y5 = 1
Дерево решений и таблица истинности для этой системы в точности совпадают с деревом и таблицей, изображенными на рис. 4. С учетом подстановки отметим, что выражение (Х1 + Х2) равно единице в трех случаях (за исключением варианта, когда обе переменные равны нулю).
Поскольку переменные Y независимы, то для первой строки таблицы истинности, показанной на рис. 4, число различных комбинаций равно 35, для второй строки - 34 и т.д. Общее число различных комбинаций равно 35 + 34 + 33 + 32 + 31 + 30 = 364.
Задание 9. Нужно найти количество решений системы уравнений (, Задание 4)
(^ ^ Ъ) ■ (-X ^ Xз) ■ № ^ X) ■ (-X ^ Кз) = 1 № ^ Y2) ■ (У1 ^ Yз) ■ (-Г1 ^ Y4) ■ (У1 ^ Y5) = 1 (-X + Y 1) ■ (-X + Y5) = 1
Для X и Y имеем следующие деревья решений
Рис. 9. Задание 8
С учетом третьего уравнения получаем следующие четыре набора комбинаций:
А - С: 4 * 4 = 16 ((-£1 + Y 1) ■ (-X + Y5) = (0 + 1) ■ (0 + 1) = 1) В - С: 4 * 4 = 16 ((-X + Y 1) ■ (-X + Y5) = (1 + 1) ■ (1 + 1) = 1) А - D: = 0 (0 + 0) ■ (-X + Y5) = 0) В - D: 4 * 4 = 16 (1 + 0) ■ (1 + Y5) = 1) Всего получается 48 наборов решений.
Задание 10. Нужно найти количество решений системы уравнений (^1 = Ъ) + (Xз = X)) ■ = Ъ) + -фз = X4)) =1 ((Xз = X4) + (X5 = X6)) ■ (-(X = X) + -(X = X6)) =1 ((X5 = X6) + ^7 = X«)) ■ (-(X = X6) + -(^7 = X8)) =1
((X7 = X8) + (X9 = Xlo)) ■ (-^7 = X8) + = Xlo)) =1 Проведем замену: (Xl = Ъ) = Yl (Xз = X4) = Y2
(Х5 = Х) = Yз (Х7 = Х8) = Y4 (Х9 = Х10) = Y5
(У^2) ■ (-Ъ + ^)=1
(Y2+Yз) ■ № + -Тз)=1
(Yз+Y4) ■ № + ^)=1
(Y4+Y5) ■ (^4 + ^)=1
На рисунке 10 показано дерево решений
У1 У2 УЗ У4 У5
Рис. 10. Задание 10
Задание 11. Нужно найти количество решений системы уравнений (, Пример 2)
Х1 + Х2 = 1 -Х2 + Хз = 1
На рисунке 11 показано дерево решений. Мы ограничились четырьмя уровнями вместо десяти, так как очевидно, что F1(N) = 1 и F0(N) = N. Тогда Р(Ы) = Р1(Ы) + БоСЫ) = 1 + N. В нашем случае Р(10) = 1 + 10 = 11.
Рис. 11. Задание 11
Задание 12. Нужно найти количество решений системы уравнений (, Пример з)
(Х1 = Х2) + (Х2 = Хз) = 1
(Х1 = Хз) + (Хз = Х4) (Х1 = Х4) + (Х4 = Х5) (Х1 = Х5) + (Х5 = Х6) (Х1 = Х6) + (Х6 = Х7) (Х1 = Х7) + (Х7 = Х8) (Х1 = Х) + (Х8 = Х9) (Х1 = Х9) + (Х9 = Х10) (Х1 = Х10) = 0
Рис. 12. Задание 12
Построив дерево решений из «1» (ограничимся пятью уровнями), заметим, что Fl(N) = N. Причем значения Хн состоят из N-1 значений «0» и одного значения «1». Однако последнее уравнение в нашей системе запрещает значение «1» для Х10. Поэтому число решений Fl(10) = 10 - 1. Нетрудно заметить, что дерево решений из «0» будет симметричным (вместо нулей будут единицы). Поэтому F0 = 10 - 1. Окончательно
F(N) = 2 х 9 = 18.
Задание 13. Нужно найти количество решений системы уравнений (, Пример 4)
- (Х1 = Х2) + (Хз = Х4) = 1
- (Хз = Х4) + (Х5 = Х) = 1
- (Х = Х) + (Х7 = Х) = 1
- (Х7 = Х8) + (Х9 = Х10) = 1
Проведем замену:
(Х1 = Х2) = Yl
(Х5 = Х) = Yз
(Х7 = Х8) = Y4
(Х9 = Х10) = Y5
Перепишем систему уравнений с учетом замены:
Из задания 11 видно, что F(5) = 5 + 1 = 6. Таблица истинности представлена на рис. 13.
У1 У2 УЗ У4 У5
Рис. 13. Задание 13
С учетом подстановки отметим, что выражение ^ = X2) равно единице (или нулю) в двух случаях (когда значения переменных совпадают). С учетом независимости переменных для каждой строки таблицы получаем, что число наборов решений равно 25 = 32. Общее число наборов решений равно 6 * 32 = 192.
Задание 14. Нужно найти количество решений системы уравнений (, Задание 1)
((Х = Ъ) ■ (Xз = X4)) + (4X1 = Ъ) ■ -(X = X)) =0 ((Xз = X4) ■ (X5 = X6)) + (4X3 = X4) ■ -(X = X6)) =0
((X5 = X) ■ (X7 = X8)) + (-(X = X6) ■ 4X7 = X8)) =0 ((X7 = X8) ■ (X9 = X«,)) + (-(^7 = X8) ■ ^9 = Xlo)) =0 Проведем замену:
Ъ) = Yl (X = ^4) = Y2
(X5 = X6) = Yз ^7 = X8) = Y4 ^9 = Xlo) = Y5
Перепишем систему уравнений с учетом замены:
(УЛ) + (-У« ■ -У2)=0
(Y2 Yз) + (-У2 ■ -У3)=0 (У3-У4) + (-У3 ■ -У4)=0 (У4-У5) + (-У4 ■ -У5)=0
(У2 = Yз) = 0 (Уз = У4) = 0 (У4 = У5) = 0
На рисунке 14 показано дерево решений
У1 У2 УЗ У4 У5
Рис. 14. Задание 14
С учетом подстановки отметим, что выражение (Х1 = Х2) равно единице (или нулю) в двух случаях (когда значения переменных совпадают). С учетом независимости переменных для каждого дерева получаем, что число наборов решений равно 25 = з2. Общее число наборов решений равно 64.
Задание 15. Нужно найти количество решений системы уравнений (, Задание 2)
(Х4 Х5) + (-Х4 -Х5) + (Х4 = Х) = 1
(Х5 Х) + (-Х -Х6) + (Х5 = Х7) = 1
(X Х7) + (-Х -Х7) + (Х = Х8) = 1
(Х7 Х) + (-Х7 -Х8) + (Х7 = Х9) = 1
(Х8 Х9) + (-Х -Х9) + (Х8 = Х10) = 1
(Х1 = Х2) + (Х1 = Хз) = 1
(Х = Хз) + (Х2 = Х4) = 1
(Хз = Х4) + (Хз = Х5) = 1
(Х4 = Х5) + (Х4 = Х) = 1
(Х5 = Х6) + (Х5 = Х7) = 1
(Х = Х7) + (Х6 = Х8) = 1
(Х7 = Х8) + (Х7 = Х9) = 1
(Х = Х9) + (Х8 = Х10) = 1
Но эта система повторяет систему из задания 5, только без условия ограничения и для N = 10. Тогда число решений равно F(N) = F1(N) + F0(N) = N + N. При N = 10 получаем F(N)= 20.
Задание 16. Нужно найти количество решений системы уравнений (, Задание 3)
(Х1 Х2) + (-Х1 -Х2) + (Х1 = Хз) = 1
(Х2 Хз) + (-Х -Хз) + (Х2 = Х4) = 1
(Хз Х4) + (-Хз -Х4) + (Хз = Х5) = 1
(Х4 Х5) + (-Х -Х5) + (Х4 = Хб) = 1
(Х5 Хб) + (-Х -Хб) + (Х5 = Х7) = 1
(Хб Х7) + (-Хб -Х7) + (Хб = Х8) = 1
(Х7 Х8) + (-Х7 -Х8) + (Х7 = Х9) = 1
(Х8 Х9) + (-Х8 -Х9) + (Х8 = Х10) = 0
Эту систему уравнений, как и в предыдущем задании, можно переписать в виде:
(XI = Х2) + (XI = Хз) = 1 (Х = Хз) + (Х2 = X) = 1 (Хз = X) + (Хз = Х5) = 1 (X = Х5) + (Х4 = Хб) = 1 (Х5 = Хб) + (Х5 = Х7) = 1 (Хб = Х7) + (Хб = Х8) = 1 (Х = Х8) + (Х7 = Х9) = 1 (Х = Х9) + (Х8 = Ххс) = 0
Из последнего уравнения легко проверить, что после N = 8 число решений перестает возрастать. Тогда F(10) = F(8) = 8 + 8 = 16.
Задание 17. Нужно найти количество решений системы уравнений (, Задание 4)
(Х1 Х2) + (-Х1 -Х2) + (Х2 Хз) + (-Х2 -Хз) = 1
(Х2 Хз) + (-Х2 -Хз) + (Хз Х) + (-Хз ■ -Х4) = 1
(Хз Х) + (-Хз -Х4) + (Х4 Х5) + (-Х4 -Х5) = 1
(Х4 X) + (-Х -Х5) + (Х5 Хб) + (-Х5 -Хб) = 1
(Х5 Хб) + (-Х -Хб) + (Хб Х7) + (-Хб ■ -Х7) = 1
(Хб Х7) + (-Хб -Х7) + (Х7 Х8) + (-Х7 -Х8) = 1
(Х7 Х) + (-Х7 -Х8) + (Х8 Х9) + (-Х8 -Х9) = 1
(Х8 Х9) + (-Х8 -Х9) + (Х9 Х10) + (-Х9 ■ -Х10) = 1
Заметим, что систему уравнений можно переписать в виде:
(Х= Х2) + (X = Хз) = 1 (Х= Хз) + (X = Х) = 1 (Хз= Х4) + (Х4 = Х5) = 1 (Х = Х5) + (Х5 = Хб) = 1 (Х5 = Хб) + (Хб = Х7) = 1
(Хб = Х7) + (Х7 = X) = 1 (Х7 = Х8) + (Х8 = Х9) = 1 (Хв = X 9) + (Х9 = Х10) = 1
На рисунке 15 дерево построено до пятого уровня и видно, что число решений описывается числами Фибоначчи, то есть Fl(N) = Fl(N-1) + Fl(N-2). Тогда Fl(10) = 89. Легко проверить, что для F0(N) дерево будет симметрично. Поэтому Fo(10) = 89. Б(10) = р1(10) + Ро(10) = 89 + 89 =178.
Рис. 15. Задание 17
Задание 18. Нужно найти количество решений системы уравнений (, Задание 5)
(Х1 Х2) + (-Х1 -Х2) + (Х2 Хз) + (-Х2 ■ -Хз) = 1
(Х2 Хз) + (-Х -Хз) + (Хз Х4) + (-Хз -Х4) = 1
(Хз Х4) + (-Хз -Х4) + (Х4 Х5) + (-Х4 ■ -Х5) = 1
(Х4 Х5) + (-Х4 -Х5) + (Х Хб) + (-Х5 ■ -Хб) = 1
(Х5 Хб) + (-Х5 -Хб) + (Хб Х7) + (-Хб ■ -Х7) = 1
(Хб Х7) + (-Хб -Х7) + (Х7 Х8) + (-Х7 ■ -Х8) = 1
(Х7 Х8) + (-Х7 -Х8) + (Х8 Х9) + (-Х8 -Х9) = 1
(Х8 Х9) + (-Х8 -Х9) + (Х9 Х10) + (-Х9 ■ -Х10) = 0
Заметим, что систему уравнений можно переписать в виде:
(Х= Х2) + (Х2 = Х3) = 1 (Х2= Хз) + (Хз = Х4) = 1
(Хз= Х) + (Х4 = Х5) = 1 (Х = Х5) + (Х5 = Хб) = 1 (Х = Хб) + (Хб = Х7) = 1 (Хб = Х7) + (Х7 = Х8) = 1 (Х7 = Х8) + (Х8 = Х9) = 1 (Х8 = Х 9) + (Х = Х10) = 0
Задание 18 похоже на задание 17, однако последнее уравнение приводит к тому, что начиная с седьмого уровня число решений не увеличивается. В результате F(10) = Fl(10) + Fo(10) = Fl(7) + Fo(7) = 21 + 21 = 42.
Задание 19. Нужно найти количество решений системы уравнений (, Задание б)
(Х= Х2) + (Х = Х10) = 1 (Х= Хз) + (Х2 = Х10) = 1 (Хз= Х4) + (X = Х10) = 1 (Х = Х5) + (Х = Х10) = 1 (Х = Хб) + (Х5 = Х10) = 1 (Хб = Х7) + (Хб = Х10) = 1 (Х7 = Х) + (Х = Х10) = 1 (Х8 = Х9) + (Х = Х10) = 1 (Х9 = Х10) + (Х9 = Х10) = 1 (Х = Х10) = 0
- - - -*- - - -*-о
Рис. 1б. Задание 19
Деревья решений для получения F1(N) и F0(N) показаны на рис. 1б. Однако уравнение (Х9 = Х10) = 1 не может быть выполнено. Поэтому система уравнений не имеет решений.
Задание 20. Нужно найти количество решений системы уравнений (, Задание 7)
(Х ^ Х2) + (Х ^ Хз) = 1 (Х2 ^ Хз) + (Х2 * Х4) = 1 (Хз ^ Х4) + (Хз ^ Х5) = 1 (Х ^ Х5) + (Х4 ^ Хб) = 1 (Х5 ^ Хб) + (Х5 ^ Х7) = 1 (Хб ^ Х7) + (Хб ^ Х8) = 1
(X7 ^ Xs) + (X7 ^ X9) = 1 (Xs ^ X9) + (Xs ^ X10) = 1
На рисунке 17 показано дерево решений из «1».
Рис. 17. Задание 20 Рис. 18. Задание 20
Вместо десяти уровней мы ограничились пятью, так как задача схожа с заданием 17. Однако из «0» дерево будет выглядеть иначе (рис. 18).
Заметим, что F0(N) = Fx(N+1) - 1. Тогда Fx(10) = 89, а F0(10) = Fx(11) - 1 = 144 - 1. Итого, F(10) = F1(10) + F0(10) = 89 + 143 = 232.
В заключение приведем программу на бейсике VBA, с помощью которой можно решать системы логических уравнений. Программа может понадобиться при составлении новых систем уравнений. На рисунке 19 показана программа, с помощью которой решается система уравнений из задания 7.
В программе, показанной на рис. 19, массив m и переменная c содержат значения переменных, удовлетворяющих системе уравнений из задания 7. Программа выдает ответ 68. В программе используется факт, что число различных наборов значений n логических переменных равно 2n. Для получения всех наборов нужно выполнить цикл от 0 до 2n-1. Переменная цикла на каждом шаге переводится в двоичную систему, результат записывается в массив m, и затем уже проверяются условия из системы уравнений. Для решения другой системы уравнений достаточно поменять размерность массива m, изменить значение переменной vg (равна размерности) и поменять условия проверки.
Dim m(S) As Integer, k As Integer, j. As Integer. _ j As Integer. N As Integer, vg As Integer Dim с As String vg=S j-0
For 1 To 2 ■""■ vg "Цикл по ^ от 1 до 2n. где n=,.g For k = 1 To vg
N = }.- 1: Двоично e пр e ц ставл e нне начинается с нуля k= 1
Do "^Tiils N > 0 "Перевод e двоичную сЯстему m(k) = N Mod 2 К = N ■ 2 k=k+ ! Loop
Ifim(l) О m(2) Or m(l)0- ni(3)) And_ "Условия уравнении (m{2) c= "" "Переменная с на каждом шаге оудет содержать решение системы For k= 1 То vg с = с - Foimat{m(k)j Next k j-j-1 End If Next I. Ms^Eox i "Количество решений VvVvVlVvVvv- -1 i Рис. 19. Программа для задания 7 1. Крылов С.С. ЕГЭ 2014. Информатика. Тематические тестовые задания / С.С. Крылов, Д.М. Ушаков. - М.: Изд-во «Экзамен». - 245 с. 2. Сайт К.Ю. Полякова. Режим доступа: http://kpolyakov.namd.-ru/download/inf-2011-14.pdf 3. Методический сертифицированный курс фирмы «1С» «Подготовка к ЕГЭ по информатике. Модуль 1». - М.: Изд-во «1С». - 218 с. 4. Успешно сдать ЕГЕ по информатике. Режим доступа: http://infoegehelp.ru/index.php?Itemid=77&id=103&option=com_con- Решение уравнения 1.Перейти к префиксной форме записи уравнения, заменив обозначения отрицаний на ¬ 2.Построить заголовок таблицы истинности специального вида 3.Заполнить строки таблицы истинности для всех сочетаний А и В, подставляя вместо X - 0 или 1. 4.Сформировать таблицу истинности для X = F (А,B) 5.По таблице истинности определить вид функции X, при необходимости воспользовавшись методами построения СКНФ и СДНФ, которые будут рассмотрены ниже.
Построение таблицы истинности специального вида ¬((А+B)·(X A·B))=¬(B+¬(X A))
Таблица истинности X=F(A, B) ABX Соответствует отрицанию импликации В в А ОТВЕТ:
Комбинационные схемы логических устройств Базисные элементы (ГОСТ): 1 А В Дизъюнкция А В Эквивалентность & А В Конъюнкция M2 А В XOR
Комбинационные схемы логических устройств Базисные элементы (ГОСТ): 1 А В Импликация & А В Элемент Шеффера & А В Коимпликация 1 А В Элемент Вебба
Пример схемы F 1 & 1 & & 1M2 B A
Решение схем 1 Вариант – преобразование схемы в сложное логическое выражение и затем – упрощение его по законам логики. 2 Вариант – построение таблицы истинности а затем, при необходимости, построение через СКНФ или СДНФ (см. ниже). Рассмотрим второй вариант, как более простой и понятный.
Построение таблицы истинности AB A + B + · B B · A + A B A + · ·
Таблица истинности F(A, B) ABX Соответствует отрицанию импликации В в А ОТВЕТ:
СДНФ и СКНФ (определения) Элементарной конъюнкцией называется конъюнкция нескольких переменных, взятых с отрицанием или без отрицания, причем среди переменных могут быть одинаковые Элементарной дизъюнкцией называется дизъюнкция нескольких переменных, взятых с отрицанием или без отрицания, причем среди переменных могут быть одинаковые Всякую дизъюнкцию элементарных конъюнкций назовем дизъюнктивной нормальной формой (ДНФ) Всякую конъюнкцию элементарных дизъюнкций назовем конъюнктивной нормальной формой (ДНФ)
СДНФ и СКНФ (определения) Совершенной дизъюнктивной нормальной формой (СДНФ), называется ДНФ, в которой нет одинаковых элементарных конъюнкций и все конъюнкции состоят из одного и того же набора переменных, в который каждая переменная входит только один раз (возможно с отрицанием). Совершенной конъюнктивной нормальной формой (СКНФ), называется КНФ, в которой нет одинаковых элементарных дизъюнкций и все дизъюнкции состоят из одного и того же набора переменных, в который каждая переменная входит только один раз (возможно с отрицанием).
Алгоритм получения СДНФ по таблице истинности 1.Отметить строки таблицы истинности в последнем столбце которых стоят 1. 2.Выписать для каждой отмеченной строки конъюнкцию всех переменных следующим образом: если значение переменной в данной строке равно 1, то в конъюнкцию включать саму эту переменную, если равно 0, то ее отрицание. 3.Все полученные конъюнкции связать в дизъюнкцию.
Алгоритм получения СКНФ по таблице истинности 1.Отметить строки таблицы истинности в последнем столбце которых стоят 0. 2.Выписать для каждой отмеченной строки дизъюнкцию всех переменных следующим образом: если значение переменной в данной строке равно 0, то в конъюнкцию включать саму эту переменную, если равно 1, то ее отрицание. 3.Все полученные дизъюнкции связать в конъюнкцию.
Пример построения СKНФ XY F(X,Y) Отметить нули 2. Дизъюнкции: X + Y 3. Конъюнкция: (X + Y) · (X + Y)
