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

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


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

© IT-EGE.cf,2014

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)  (x2  x3) = 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

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

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

  1. перепишем уравнения с помощью более простых обозначений:



  1. заметим, что последние 3 уравнения независимы друга от друга, и вся система связана только через первое уравнение

  2. рассмотрим второе уравнение



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







  1. аналогичные уравнения 3-4 тоже имеют по три решения

  2. теперь рассмотрим множество решений системы уравнений 2-3



при ограничении, которое накладывается первым уравнением:



  1. поскольку импликация дает ложное значение (0) только для случая 10, первое уравнение в исходной системе запрещает комбинацию .

  2. рассмотрим решение уравнений 2 и 3:





(0,1,1)

(1,0,1)

(1,1,0)

(0,1,1)

(1,0,1)

(1,1,0)

Эти уравнения независимы, поэтому система уравнений 2-3 (без дополнительных ограничений) имеет 33=9 решений

При ограничении :

  • в случае имеем только одно решение системы, когда в уравнении  2, то есть

  • для двух решений уравнения 3, когда , подходят все 3 отдельных решения уравнения 2

поэтому количество решений системы уравнений 2-3 при ограничении вычисляется как 1 + 3 + 3 = 7 решений

  1. рассуждая аналогично, подключаем уравнение 4 и ограничение , получаем, что количество решений системы уравнений 2-4 при ограничении вычисляется как 1 + 7 + 7 = 15 решений

  2. Ответ: 15.

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

  1. п. 1-4 совпадают с предыдущим вариантом решения

  2. построим правило отображения троек переменных.


1 уравнение

2 уравнение

3 уравнение


x2y2z2

x3y3z3

x1y1z1


011
прямая со стрелкой 38
011
прямая со стрелкой 43 прямая со стрелкой 44
011

101

110
прямая со стрелкой 48 прямая со стрелкой 49 прямая со стрелкой 55 прямая со стрелкой 59 прямая со стрелкой 60 прямая со стрелкой 61


прямая со стрелкой 42прямая со стрелкой 52прямая со стрелкой 57

101

101
прямая со стрелкой 50 прямая со стрелкой 51 прямая со стрелкой 53 прямая со стрелкой 54 прямая со стрелкой 58

110

110
прямая со стрелкой 56


Если бы не было никаких ограничений, то данная система имела бы 9 решений.

  1. так как система имеет ограничения в виде первого уравнения,

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

то убираем все связи где выше указанные импликации ложны, а именно:

для (x1x2): x1 = 1, x2 = 0,

(x2x3): x2 = 1, x3 = 0.


1 уравнение

2 уравнение

3 уравнение


x2y2z2

x3y3z3

x1y1z1


011
прямая со стрелкой 84
011
прямая со стрелкой 82 прямая со стрелкой 81
011

101

110
прямая со стрелкой 77 прямая со стрелкой 76 прямая со стрелкой 73 прямая со стрелкой 75


прямая со стрелкой 89

101

101
прямая со стрелкой 94 прямая со стрелкой 93 прямая со стрелкой 92 прямая со стрелкой 91 прямая со стрелкой 90

110

110
прямая со стрелкой 97


  1. Заполняем таблицу, вычисляя количество решений при подключении каждого последующего уравнения.

    xyz

    1 уравнение

    2 уравнение

    3 уравнение

    011

    1

    1

    1

    101

    1

    3

    7

    110

    1

    3

    7

  2. Складываем все результаты: 1 + 7 + 7 = 15.

  3. Ответ: 15.
  1   2   3   4   5   6   7   8   9   ...   20

Похожие:

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

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


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

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