Тема : Преобразование логических выражений icon

Тема : Преобразование логических выражений



НазваниеТема : Преобразование логических выражений
страница1/15
Дата конвертации17.09.2012
Размер1.2 Mb.
ТипДокументы
  1   2   3   4   5   6   7   8   9   ...   15

© К. Поляков, 2009-2012

B15 (высокий уровень, время – 10 мин)


Тема: Преобразование логических выражений.

Про обозначения

К сожалению, обозначения логических операций И, ИЛИ и НЕ, принятые в «серьезной» математической логике (, , ¬), неудобны, интуитивно непонятны и никак не проявляют аналогии с обычной алгеброй. Автор, к своему стыду, до сих пор иногда путает и . Поэтому на его уроках операция «НЕ» обозначается чертой сверху, «И» – знаком умножения (поскольку это все же логическое умножение), а «ИЛИ» – знаком «+» (логическое сложение).
В разных учебниках используют разные обозначения. К счастью, в начале задания ЕГЭ приводится расшифровка закорючек (, , ¬), что еще раз подчеркивает проблему.

Что нужно знать:

  • условные обозначения логических операций

¬ A, не A (отрицание, инверсия)

A  B, A и B (логическое умножение, конъюнкция)

A  B, A или B (логическое сложение, дизъюнкция)

AB импликация (следование)

AB, эквиваленция (эквивалентность, равносильность)

  • таблицы истинности логических операций «И», «ИЛИ», «НЕ», «импликация», «эквиваленция» (см. презентацию «Логика»)

  • операцию «импликация» можно выразить через «ИЛИ» и «НЕ»:

AB = ¬ A  B или в других обозначениях AB =

  • операцию «эквиваленция» также можно выразить через «ИЛИ» и «НЕ»:

AB = ¬ A  ¬ B  A  B или в других обозначениях AB = gif" name="object6" align=absmiddle width=77 height=18>

  • если в выражении нет скобок, сначала выполняются все операции «НЕ», затем – «И», затем – «ИЛИ», потом – «импликация», и самая последняя – «эквиваленция»

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

  • логическая сумма A+B+C+… равна 0 (выражение ложно) только тогда, когда все слагаемые равны 0 (а в остальных случаях равна 1)

  • правила преобразования логических выражений (законы алгебры логики):

Закон

Для И

Для ИЛИ

двойного отрицания



исключения третьего





исключения констант

A · 1 = A; A · 0 = 0

A + 0 = A; A + 1 = 1

повторения

A · A = A

A + A = A

поглощения

A · (A + B) = A

A + A · B = A

переместительный

A · B = B · A

A + B = B + A

сочетательный

A · (B · C) = (A · B) · C

A + (B + C) = (A + B) + C

распределительный

A + B · C = (A + B) · (A + C)

A · (B + C) = A · B + A · C

де Моргана




^

Пример задания:


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

(x1  x2)  (x2  x3)  (x3  x4)= 1

1  у2)  (у2  у3)  (у3  у4) = 1

(y1  x1)  (y2  x2)  (y3  x3)  (y4  x4) = 1

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

Решение:

  1. видим, что первые два уравнения независимы друг от друга (в первое входят только x1, x2, …, x4, а во второе – только y1, y2, …, y4)

  2. третье уравнение связывает первые два, поэтому можно поступить так:

  • найти решения первого уравнения

  • найти решения второго уравнения

  • найти множество решений первых двух уравнений

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

  1. найдем решения первого уравнения; каждая из логических переменных x1, x2, …, x4 может принимать только два значения: «ложь» (0) и «истина» (1), поэтому решение первого уравнения можно записать как битовую цепочку длиной 4 бита: например, 0011 означает, что
    x1 = x2 0 и x3 = x4 1

  2. вспомним, что импликация x1x2 ложна только для x1 = 1 и x2 = 0, поэтому битовая цепочка, представляющая собой решение первого уравнения, не должна содержать сочетания «10»; это дает такие решения (других нет!):

(x1, x2, x3, x4) = 0000 0001 0011 0111 1111

  1. видим, что второе уравнение полностью совпадает по форме с первым, поэтому все его решения:

(y1, y2, y3, y4) = 0000 0001 0011 0111 1111

  1. поскольку первые два уравнения независимы друг от друга, система из первых двух уравнений имеет 5·5=25 решений: каждому решению первого соответствует 5 разных комбинаций переменных y1, y2, …, y4, которые решают второе, и наоборот, каждому решению второго соответствует 5 разных комбинаций переменных x1, x2, …, x4, которые решают первое:

(y1, y2, y3, y4) = 0000 0001 0011 0111 1111

(x1, x2, x3, x4) = 0000 0000 0000 0000 0000

0001 0001 0001 0001 0001

0011 0011 0011 0011 0011

0111 0111 0111 0111 0111

1111 1111 1111 1111 1111

  1. теперь проверим, какие ограничения накладывает третье уравнение; вспомнив формулу, которая представляет импликацию через операции «НЕ» и «ИЛИ» (), можно переписать третье уравнение в виде

(y1  x1)  (y2  x2)  (y3  x3)  (y4  x4) = 1

  1. импликация y1x1 ложна только для y1 = 1 и x1 = 0, следовательно, такая комбинация запрещена, потому что нарушает третье уравнение; таким образом, набору с y1 = 1:

(y1, y2, y3, y4) = 1111

соответствует, с учетом третьего уравнения, только одно решение первого, в котором x1 = 1

(y1, y2, y3, y4) = 1111

поэтому множество решений «редеет»:


(y1, y2, y3, y4) = 0000 0001 0011 0111 1111

(x1, x2, x3, x4) = 0000 0000 0000 0000

0001 0001 0001 0001

0011 0011 0011 0011

0111 0111 0111 0111

1111 1111 1111 1111 1111

  1. аналогично двигаемся дальше по третьему уравнению; второй сомножитель равен 0, если импликация y2x2 ложна, то есть только для y2 = 1 и x2 = 0, это «прореживает» предпоследний столбец:

(y1, y2, y3, y4) = 0000 0001 0011 0111 1111

(x1, x2, x3, x4) = 0000 0000 0000

0001 0001 0001

0011 0011 0011

0111 0111 0111 0111

1111 1111 1111 1111 1111

  1. аналогично проверяем еще два ограничения, отбрасывая все решения, для которых y3 = 1 и x3 = 0, а также все решения, для которых y4 = 1 и x4 = 0:

(y1, y2, y3, y4) = 0000 0001 0011 0111 1111

(x1, x2, x3, x4) = 0000

0001 0001

0011 0011 0011

0111 0111 0111 0111

1111 1111 1111 1111 1111

  1. итак, остается одно решение при (y1, y2, y3, y4)=1111, два решения при (y1, y2, y3, y4)=0111, три решения при(y1, y2, y3, y4)=0011, четыре решения при(y1, y2, y3, y4)=0001 и 5 решений при (y1, y2, y3, y4)=0000

  2. всего решений 1+2+3+4+5=15.
  1   2   3   4   5   6   7   8   9   ...   15




Похожие:

Тема : Преобразование логических выражений iconПроверочная работа «Преобразование логических выражений»
Выполнить вычисления по логической схеме и записать соответствующее логическое выражение
Тема : Преобразование логических выражений iconТема : Преобразование логических выражений
Автор, к своему стыду, до сих пор иногда путает  и . Поэтому на его уроках операция «НЕ» обозначается чертой сверху, «И» – знаком...
Тема : Преобразование логических выражений iconТема : Преобразование логических выражений
Автор, к своему стыду, до сих пор иногда путает  и . Поэтому на его уроках операция «НЕ» обозначается чертой сверху, «И» – знаком...
Тема : Преобразование логических выражений iconТема : Преобразование логических выражений. Формулы де Моргана
Автор, к своему стыду, до сих пор иногда путает  и . Поэтому на его уроках операция «НЕ» обозначается чертой сверху, «И» – знаком...
Тема : Преобразование логических выражений iconТема : Составление запросов для поисковых систем с использованием логических выражений
Тема: Составление запросов для поисковых систем с использованием логических выражений
Тема : Преобразование логических выражений iconТематическое планирование учебного материала по алгебре в 10-м классе
Тема № Преобразование тригонометрических выражений 13 ч. Контрольная работа №4
Тема : Преобразование логических выражений iconПостроение таблиц истинности логических выражений Приоритет логических операций
При вычислении значения логического выражения (формулы) логические операции вычисляются в определенном порядке, согласно их приоритету:...
Тема : Преобразование логических выражений iconУрок путешествия: «Осенняя прогулка» Тема урока: «Преобразование рациональных выражений»
Оборудование: индивидуальные карточки ( в форме осенних листьев и цветов), тест, карточки для проведения рефлексии, компьютер
Тема : Преобразование логических выражений iconТема: «Преобразование выражений, содержащих квадратные корни» (Алгебра, 8 класс)
Внести множитель под знак корня или вынести множитель из-под знака корня (на этом этапе можно обращаться за помощью)
Тема : Преобразование логических выражений iconПреобразование степенных и дробно – иррациональных выражений

Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©podelise.ru 2000-2014
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы

Разработка сайта — Веб студия Адаманов