Кондрашова Е.В. МБОУ «СОШ п. Пробуждение» ЭМР Саратовской области

Сложность – высокая. Примерное время решения – 5-10 мин. Тема: Основы логики Подтема: Анализ логических выражений Что проверяется: Умение анализировать логические выражения. Умение описать на естественном языке множество значений логических переменных, при которых заданный набор логических выражений истинен.

Эта задача – одна из самых сложных в экзамене, если не самая сложная. Для ее решения ученик должен уметь - преобразовывать логические выражения (включая выполнение замены переменных); - переводить формальное описание, в виде системы логических условий, на нормальный, "человеческий" язык и - подсчитать число двоичных наборов, удовлетворяющих заданным условиям. После того, как выяснено, что за наборы удовлетворяют системе, подсчет их числа относительно прост. Наиболее трудным для усвоения является второе из перечисленных требований – оно не формализуется, от ученика, как правило, требуется догадка.

Точного алгоритма действий, гарантированно приводящего к успеху здесь нет. Первая цель – понять, что собой представляет множество решений системы. Для этого систему бывает полезно преобразовать (упростить) систему, используя тождественные преобразования и замены переменных. Затем – подсчитать количество элементов во множестве решений. Во многих случаях система состоит из однотипных уравнений, каждое из которых связывает небольшое число переменных (две-три-четыре), при том, что в системе может быть 10 и более переменных. Обычно, количество переменных не является источником сложности, оно является параметром решения. Если не получается решить задачу в общем виде, можно попробовать перебрать все решения для системы с небольшим количеством переменных. Это может подсказать, как выглядит решение в общем виде.

условные обозначения логических операций ¬ A, не A - (отрицание, инверсия) A B, AB, A и B - (логическое умножение, конъюнкция) A B, A+B, A или B - (логическое сложение, дизъюнкция) A B - импликация (следование) A B - эквиваленция (эквивалентность, равносильность)

таблицы истинности логических операций «И», «ИЛИ», «НЕ», «импликация», «эквиваленция» операцию «импликация» можно выразить через «ИЛИ» и «НЕ»: A B = ¬ A B или в других обозначениях операцию «эквиваленция» также можно выразить через «ИЛИ» и «НЕ»: A B = ¬ A ¬ B A B или в других обозначениях если в выражении нет скобок, сначала выполняются все операции «НЕ», затем – «И», затем – «ИЛИ», потом – «импликация», и самая последняя – «эквиваленция»

логическое произведение ABC… =1 (выражение истинно) только тогда, когда все сомножители равны 1 (в остальных случаях 0) логическая сумма A+B+C+…=0 (выражение ложно) только тогда, когда все слагаемые равны 0 (в остальных случаях 1) правила преобразования логических выражений (законы алгебры логики):

6*. Сколько различных решений имеют уравнения? А) (А В)(B C)(C D)=O … Д) A B C D E H=1 Обратите внимание, что число решений логических уравнений всегда конечно. Это связано с тем, что каждая переменная может принимать только 2 значения «0» и «1». Уравнение с n переменными имеет не более 2^n решений.

Табличный способ: Графический способ: АBCD А В С D реш. 7 реш. АBCD Ответ: 4+7=11 реш.

ABCDEH= 1 Табл. истинности для импликации: АВАB Представим таблицу истинности как отображение множеств: А АB F(0)=F(1) F(1)=2*F(0)+F(1)

A B C D E H = 1 Построим таблицу для определения количества нулей и единиц: КОЛ-ВО значений КОЛИЧЕСТВО ПОСЛЕ ВЫПОЛНЕНИЯ ДЕЙСТВИЯ АIIIIIIIVV IIIIIIIVV В каждом столбике в сумме получается очередная степень числа 2. После V действия сумма «0» и «1» равна 64 (2^n для шести переменных).

В выражении используются две операции импликация и конъюнкция. Строим отображения множеств для этих операций:

Ответ: кол-во решений отображающихся в «1» Для импликации: F(0)=F(1) F(1)=2*F(0) + F(1) Для конъюнкции: F(0)=2*F(0)+F(1) F(1)=F(1)

Расставим порядок действий: Заметим: выражения в первой и второй скобках не зависят друг от друга, вторая скобка частично повторяет первую:

Для 1-й скобки:Для 2-й скобки: Для последнего действия: Ответ: 95 (в соотв. с табл. истинности импликации).

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

Все уравнения системы однотипны. Каждое уравнение содержит 3 переменные. Зная x 1 и x 2 можно найти x 3. x1x1 x2x2 x3x Строим правило отображения с помощью таблицы:

По таблице строим ориентированный граф: и правила счета: F(00)=F(00) F(01)=F(00)+F(10) F(10)=F(01)+F(11) F(11)=F(01)+F(11)

Ответ: =232 решения

Ответ: =122 решения

Сколько различных решений имеет система логических уравнений (x 1 x 2 ) (x 1 x 3 ) (x 2 x 3 ) = 0 (x 3 x 4 ) (x 3 x 5 ) (x 4 x 5 ) = 0 (x 5 x 6 ) (x 5 x 7 ) (x 6 x 7 ) = 0 (x 7 x 8 ) (x 7 x 9 ) (x 8 x 9 ) = 0. В качестве ответа нужно указать количество решений. x1 x1 x2x2 x3x ) 2)2) x1x1 x3x3

в таблицу необходимо включить переменные x 1,x 3,x 5, x 7 и x 9 ; на старте имеем одно значение x 1 =0 и одно значение x 1 =1. складываем все результаты: = 162 Ответ: 162 решения. x1x3x3x5x5x7x7x9x

x 1 +x 2 ·x 3 =1 x 2 +x 3 ·x 4 =1 … x 8 +x 9 ·x 10 =1 x 1 x 2 x 2 x F(00)=F(10) F(01)=F(10) F(10)=F(11) F(11)=F(01)+F(11) x1x1 x2x2 x3x ) 2) 3) Ск-ко решений имеет система уравнений?

x1x2x2x3x3x4x4x5x5x6x6x7x7x8x8x9x9x Ответ: =73 решения.

- Мирончик Ел.А., Мирончик Ек.А. Презентация «Системы логических уравнений. Метод отображения» Метод отображений для решения систем логических уравнений (Ел.А. Мирончик века. Мирончик) архив Метод отображений для решения систем логических уравнений (Ел.А. Мирончик века. Мирончик) B15 логические уравнения – документ Word 1,9 Мб B15 логические уравнения тест на отработку решений задач В15 «Системы логических уравнений» htm - интерактивный тренажер htm - образовательный ресурс «Информатика и математика»