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

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


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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • логическое произведение 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)  (x1  x3)  (x2  x3) = 0

(x3  x4)  (x3  x5)  (x4  x5) = 0

(x5  x6)  (x5  x7)  (x6  x7) = 0

(x7  x8)  (x7  x9)  (x8  x9) = 0

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

Решение (последовательное включение уравнений):

  1. заметим два важных момента:

    1. все 4 уравнения – однотипные

    2. первое связано со вторым только через переменную x3, второе с третьим – только через x5, третье с четвертым – только через x7

  1. разберем подробно одно первое уравнение; поскольку в нем используется операция И (конъюнкция) и правая часть равна нулю (ложное значение), имеет смысл проверить ситуации, когда первое уравнение истинно: это будет тогда, когда x2  x3, а x1 не равно этому значению, то есть в двух случаях: (x1,x2,x3)=(1,0,0) и (x1,x2,x3)=(0,1,1)

  2. поскольку логическое уравнение с тремя переменными может иметь не более 8 = 23 решений, вычитаем два решения из этого количества и находим, что первое уравнение имеет 8 – 2 = 6 решений, причем в трёх из них x3 = 0, а в трёх других x3 = 1.

  3. подключаем второе уравнение: для каждого из трёх решений первого при x3 = 0 получаем три решения второго, и для каждого из трёх решений первого при x3 = 1 получаем ещё три решения второго, всего система из двух уравнений имеет 3*3 + 3*3 = 18 решений

  4. далее продолжаем таблицу:

    число уравнений

    решений

    1

    3(при x3= 0) + 3(при x3= 1) = 6

    2

    3*3 + 3*3 = 9(при x5= 0) + 9(при x5= 1) = 18

    3

    9*3 + 9*3 = 27(при x7= 0) + 27(при x7=1) = 54

    4

    27*3 + 27*3 = 81 + 81 = 162

  5. Ответ: 162

^ Решение (метод отображений1, решение А.Н. Носкина):

  1. сначала построим таблицу, в которой переберем все варианты x1, x2, x3, поскольку в первом логическом уравнении три переменных, то таблица будет иметь 8 строк (8 = 23);

уберем из таблицы (желтая заливка) такие значения x3, при которых первое уравнение не имеет решения.

x1

x2

x3

0

0

0

1

1

0

1

1

0

0

1

1

0

1




  1. анализируя таблицу, строим правило отображения пар переменных

(например паре x1x2=00 соответствуют пары x2x3= 00 и 01).




  1. теперь построим таблицу, в которой переберем все варианты x3, x4, x5, поскольку во втором логическом уравнении три переменных, то таблица будет иметь 8 строк (8 = 23);

уберем из таблицы (желтая заливка) такие значения x5, при которых второе уравнение не имеет решения.

X3

X4

X5

0

0

0

1

1

0

1

1

0

0

1

1

0

1

  1. анализируя таблицу, строим правило отображения пар переменных, связывая с переменными первого логического уравнения



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




x1x2

x2x3

x4x5

x6x7

x8x9

00

1

1

3

9

27

01

1

2

6

18

54

10

1

2

6

18

54

11

1

1

3

9

27




  1. Складываем все результаты: 27 + 54 + 54 + 27 = 162

  2. Ответ: 162.

Решение (метод отображений, решение Ел.А. Мирончик):

  1. для построения отображения построим таблицу решения первого уравнения:

    x1

    x2

    x3

    0

    0

    0

    1

    1

    0

    1

    0

    1

    1

    0

    1

  2. уравнения связаны только через одну переменную, значит множество значений переменной x1 приведет к множеству значений переменной x3 это отображение повторится на переходе от x3 к x5, далее к x7 и x9

  3. построим отображение:



  1. в таблицу необходимо включить переменные x1,x3,x5, x7 и x9; на старте имеем одно значение x1=0 и одно значение x1=1




    X1

    X3

    X5

    X7

    X9

    0

    1

    3

    9

    27

    81

    1

    1

    3

    9

    27

    81

  2. складываем все результаты: 81 + 81 = 162

  3. ответ: 162.
  1   2   3   4   5   6   7   8   9   ...   19

Похожие:

Тема : Преобразование логических выражений iconТема : Преобразование логических выражений
Автор, к своему стыду, до сих пор иногда путает  и . Поэтому на его уроках операция «НЕ» обозначается чертой сверху, «И» – знаком...
Тема : Преобразование логических выражений iconТема : Преобразование логических выражений
Автор, к своему стыду, до сих пор иногда путает  и . Поэтому на его уроках операция «НЕ» обозначается чертой сверху, «И» – знаком...
Тема : Преобразование логических выражений iconТема: Преобразование степенных и иррациональных выражений

Тема : Преобразование логических выражений iconТема : Построение таблиц истинности логических выражений
Автор, к своему стыду, до сих пор иногда путает  и . Поэтому на его уроках операция «НЕ» обозначается чертой сверху, «И» – знаком...
Тема : Преобразование логических выражений iconТема : Построение таблиц истинности логических выражений
Автор, к своему стыду, до сих пор иногда путает  и . Поэтому на его уроках операция «НЕ» обозначается чертой сверху, «И» – знаком...
Тема : Преобразование логических выражений iconТема : Построение таблиц истинности логических выражений
Автор, к своему стыду, до сих пор иногда путает  и . Поэтому на его уроках операция «НЕ» обозначается чертой сверху, «И» – знаком...
Тема : Преобразование логических выражений iconRegexponline анализатор и конструктор регулярных выражений
Для тех, кому лень читать много букв: удобный инструмент для составления и анализа регулярных выражений. Находится по адресу
Тема : Преобразование логических выражений iconСхемная реализация сложных логических функций
Триггеры на логических элементах. Rs-триггер. Принцип работы. Схемная реализация. Таблица истинности. Временная диаграмма
Тема : Преобразование логических выражений icon12 17. Таблицы истинности логических элементов
По указанной изучить порядок работы с пакетом Electronics Workbench (ewb), ответить на контрольные вопросы, составить таблицы истинности...
Тема : Преобразование логических выражений iconКакая из логических операций является отрицанием? Какая из логических операций является конъюнкцией?
Перевести число …, представленное в десятичной системе счисления, в восьмеричную
Тема : Преобразование логических выражений icon1. Совместная работа цифровых элементов в составе узлов и устройств Транзисторно-транзисторная логика
Ттл, ttl) — разновидность цифровых логических микросхем, построенных на основе биполярных транзисторов и резисторов. Название транзисторно-транзисторный...
Вы можете разместить ссылку на наш сайт:
Документы


При копировании материала укажите ссылку ©ignorik.ru 2015

контакты
Документы