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

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



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

Ещё пример задания:


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

X1 ? X2 ? X3 ? X4 ? X5 ? X6 = 1

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


^ Решение (вариант 1, табличный метод, динамическое программирование):

  1. в левой части заданного уравнения стоят последовательно несколько операций импликации, скобок нет, поэтому порядок выполнения операций определяется приоритетом этих операций; в данном случае все операции имеют одинаковый приоритет

  2. операции, имеющие одинаковый приоритет, выполняются слева направо, то есть первой выполняется импликация X1 ? X2, а последней – последняя импликация

((((X1 ? X2) ? X3) ? X4) ? X5) ? X6

  1. каждая логическая переменная может принимать значение «истина» (1) или «ложь» (0)

  2. для набора из 6 независимых логических переменных существует 26 =64 разных комбинаций значений этих переменных

  3. рассмотрим первую импликацию, X1 ? X2; она дает в трёх случаях 1, и в одном – 0:

    X1

    X2

    X1 ? X2

    0

    0

    1

    0

    1

    1

    1

    0

    0

    1

    1

    1

  4. посмотрим, как меняется количество решений, если «подключить» следующую переменную;

    • если X1=0, то X1 ? X2 =1 (из нулей получаются единиц)

    • если X1=1, то X1 ? X2 =0 при X2 =0 и X1 ? X2 =1 при X2 =1 (из единиц получаются нулей и единиц)

  1. исходя из этого, можно составить формулы для вычисления количества нулей и количества единиц для уравнения с переменными:

,

  1. для одной переменной имеем 1 ноль и 1 единицу, поэтому начальные условия для расчёта:



  1. составим таблицу, которую будем заполнять слева направо, вычисляя число нулей и единиц по приведенным выше формулам; в таблице показано, как строится следующий столбец таблицы для :



  1. таким образом, ответ: 43 решения.

Решение (вариант 2, «с хвоста»):

  1. те же рассуждения, что и в п. 1-4 решения по варианту 1

  2. если X6 =1, то левая часть уравнения равна 1, то есть равенство выполняется; комбинаций с X6 =1 ровно половина от общего количества, то есть 32

  3. теперь проверяем варианты с X6 =0; сразу получаем, что для выполнения заданного уравнения нужно, чтобы (X1 ? X2 ? X3 ? X4 ? X5)=0; иначе получим 1 ? X6 = 1 ?0 = 0

  4. проверим отдельно случаи X5 =0 и X5 =1

  5. пусть X6 = 0 и X5 =1; в этом случае никогда не будет выполнено условие
    (X1 ? X2 ? X3 ? X4 ? X5)=0, решений нет

  6. пусть X6 = X5 =0; в этом случае условие (X1 ? X2 ? X3 ? X4 ? X5)=0 выполняется только при (X1 ? X2 ? X3 ? X4)=1; если X4 =1, это условие всегда верно, поэтому получаем еще 8 решений – 8 комбинаций, где X6 = X5 =0 и X4 =1 (1/8 всех комбинаций)

  7. теперь рассмотрим случаи, когда X6 = X5 = X4 =0; рассуждая аналогично, находим, что условие (X1 ? X2 ? X3 ? 0)=1 верно при (X1 ? X2 ? X3)=0, это сразу дает X3 =0 и
    (X1 ? X2)=1

  8. при всех известных значениях остальных переменных (X6 = X5 = X4 = X3 =0) условие
    (X1 ? X2)=1 истинно в трёх случаях: (X1,X­2) =(0,0) , (0,1) и (1,1), это дает еще 3 решения

  9. таким образом, ответ: 32 + 8 + 3 = 43 решения.

Решение (вариант 3, приведение к базису «И-ИЛИ-НЕ», Е.Н. Смирнова):

  1. те же рассуждения, что и в п. 1-4 решения по варианту 1

  2. заменяем импликацию по формуле ; на первом шаге получаем



  1. далее по той же формуле



инверсию в первом слагаемом раскроем по закону де Моргана ():



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



  1. и, применяя ту же формулу еще раз, получим уравнение



  1. при остальные 5 переменных можно выбирать любым способом, это дает 232 решения4444444

  2. при и решений нет

  3. при получаем 23 = 8 решений при (можно выбирать , и произвольно)

  4. при сразу находим, что , это дает еще 3 решения, при которых истинно выражение

  5. таким образом, ответ: 32 + 8 + 3 = 43 решения.
1   2   3   4   5   6   7   8   9   ...   13



Похожие:

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

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


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