Логика. Преобразование логических выражений Что нужно знать



страница9/10
Дата02.01.2013
Размер0.57 Mb.
ТипЗакон
1   2   3   4   5   6   7   8   9   10

Задание 11: Сколько различных решений имеет уравнение


((J → K) →(M  N  L))  ((M  N  L) → (¬J  K))  (M → J) = 1

где J, K, L, M, N – логические переменные? В ответе не нужно перечислять все различные наборы значений J, K, L, M и N, при которых выполнено данное равенство. В качестве ответа Вам нужно указать количество таких наборов.

Решение (вариант 1, использование свойств импликации):

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



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

  2. учитывая, что , и выполняя замены и , получаем

.

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







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



  1. в случае «а» последнее уравнение превращается в и не имеет решений

  2. в случае «б» имеем , тогда как и – произвольные; поэтому есть 4 решения, соответствующие четырем комбинациям и gif" name="object228" align=absmiddle width=19 height=18>

  3. в случае «в» получаем , то есть для есть единственное решение (), а для – три решения (при ; и ; и )

  4. проверяем, что среди решений, полученных в п. 7 и 8 нет одинаковых

  5. таким образом, всего есть 4 + 1 + 3 = 8 решений

  6. ответ – 8

Решение (вариант 2, использование свойств импликации, А.М. Фридлянд, УГАТУ):

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



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

  2. учитывая, что , и выполняя замены и , получаем

.

  1. преобразуем первые две скобки: , где знак означает операцию «эквивалентность». Так как это выражение должно быть истинным, значения и совпадают. Поэтому исходное уравнение распадается на 2 случая:





  1. В случае а) из первого уравнения сразу получаем, что . Тогда третье уравнение справедливо при любом , а второе имеет 7 решений (любое, кроме ).

  2. в случае б) из второго уравнения получаем: , но тогда из третьего уравнения следует, что (иначе ), а тогда и (иначе ).

  3. таким образом, всего есть 7 + 1 = 8 решений

  4. ответ – 8

Решение (вариант 3, декомпозиция, автор идеи – А. Сидоров, ЭПИ МИСИС):

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



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

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

  3. например, пусть ; тогда требуется, чтобы , по таблице истинности импликации получается, что при этом может быть любое («из лжи следует что угодно»);

  4. выполним второй шаг декомпозиции: рассмотрим отдельно варианты и

  5. при и получаем



это равенство истинно, если , а такого не может быть, то есть в этом случае решений нет

  1. при и получаем



это равенство истинно только при (иначе первая скобка равна нулю), но у нас никак не ограничены значения и поэтому получается, что при и есть 4 решения (при и всех 4-х различных комбинациях и )

  1. теперь проверяем вариант, когда ; при этом



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



  1. выполним второй шаг декомпозиции: рассмотрим отдельно варианты и

  2. при получаем , откуда сразу следует, что (3 решения: ; и )

  3. при получаем , откуда сразу следует, что (1 решение: )

  4. таким образом, уравнение всего имеет 4+3+1 = 8 решений

  5. ответ – 8

Решение (вариант 4, декомпозиция, автор идеи – А. Сидоров, ЭПИ МИСИС):

  1. та же декомпозиция, но в другом порядке

  2. сделаем сначала декомпозицию по

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



получаем



  1. учитывая, что при любом («из лжи следует все, что угодно»), находим



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



этого не может быть, потому что первая скобка равна нулю; поэтому при решений нет

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



  1. выполним декомпозицию по переменной

  2. при получаем , что верно при условии ; из всех 8-ми комбинаций значений переменных , и только одна этому условию не удовлетворяет (), поэтому имеем 7 решений

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

  4. таким образом, уравнение всего имеет 7+1 = 8 решений

  5. ответ – 8

Возможные проблемы:

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

    • нужно помнить, что импликация равна нулю только в случае , часто именно это свойство позволяет упростить решение

Решение (вариант 5, комбинированный, Т.Н. Наумова, ХМАО, Пыть-Ях, МОУ СОШ №5):

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



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



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

  2. рассмотрим первое уравнение: ; оно справедливо в двух случаях:

    1. , – любое, или , где звездочка означает, что переменная может принимать значения 0 или 1; всего получается 8 вариантов

    2. , , что дает ещё три варианта:
      – два варианта

– один вариант

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

    J

    K

    L

    M

    N








    1

    0

    0

    0

    0

    1

    1



    1

    0

    0

    0

    1

    1

    1



    1

    0

    0

    1

    0

    1

    1



    1

    0

    0

    1

    1

    1

    1



    1

    0

    1

    0

    0

    1

    1



    1

    0

    1

    0

    1

    1

    1



    1

    0

    1

    1

    0

    1

    1



    1

    0

    1

    1

    1

    0

    1




    0

    0

    1

    1

    1

    1

    0




    0

    1

    1

    1

    1

    1

    0




    1

    1

    1

    1

    1

    1

    1



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

  3. ответ – 8

Задание 12:


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

((J K) (M N L)) ((J ¬K) ¬(M N L)) (M J)= 1

где J, K, L, M, N – логические переменные? В ответе не нужно перечислять все различные наборы значений J, K, L, M и N, при которых выполнено данное равенство. В качестве ответа Вам нужно указать количество таких наборов.

Решение (вариант 1, упрощение выражения):

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



  1. попытаемся использовать замену переменных



  1. тогда

  2. с учетом этих обозначений преобразуем исходное уравнение к виду:



  1. раскрываем импликации по правилу :



  1. перемножаем первые две скобки, учитывая, что :



  1. снова раскрываем скобки



  1. возвращаемся к исходным переменным, вспоминая, что



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



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





  1. такие образом, уравнение разбивается на два:

(*)

(**)

  1. из уравнения следует, что и хотя бы одна из переменных не равна 1; поэтому уравнение (*) имеет 7 решений (за исключением случая )

  2. уравнение (**) имеет единственное решение

  3. среди решений уравнений (*) и (**) нет одинаковых (в первом случае , а во втором - ), поэтому исходное уравнение имеет 7 + 1 = 8 решений.

  4. ответ – 8.

КР «Минимизация сложных логических формул».


Вариант 1.

1. Какое логическое выражение эквивалентно выражению ¬(A B) ¬C?

1) ¬A B ¬C 2) ¬A ¬B ¬C 3) ¬A ¬B C 4) ¬A ¬B ¬C

2.Каково наименьшее целое положительное число X, при котором высказывание:

        1. > -(4 + XX) (30 > X·X) будет ложным.

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

(K L M) (¬L ¬M N) = 1 где K, L, M, N – логические переменные? В ответе не нужно перечислять все различные наборы значений K, L, M и N, при которых выполнено данное равенство. В качестве ответа вам нужно указать только количество таких наборов.



Вариант 2.

1. Какое логическое выражение эквивалентно выражению ¬(A ¬B C)?

1) ¬A B ¬C 2) ¬A B ¬C 3) ¬A (B C) 4) ¬A B ¬A ¬C

2.Каково наибольшее целое положительное число X, при котором истинно высказывание: ((X - 1) < X) (40 > X·X)

3.Укажите значения переменных K, L, M, N, при которых логическое выражение

(¬K M) (¬L M N) ложно. Ответ запишите в виде строки из четырех символов: значений переменных K, L, M и N (в указанном порядке). Так, например, строка 1101 соответствует тому, что K=1, L=1, M=0, N=1.



Вариант 3.

1. Какое логическое выражение эквивалентно выражению ¬(¬A ¬B) C?

1) ¬A B ¬C 2) A B C 3) (A B) C 4)( ¬A ¬B) ¬C

2.Каково наибольшее целое число X, при котором истинно высказывание

  1. < X·X) (X < (X-1))

3.Укажите значения переменных K, L, M, N, при которых логическое выражение

(M L) K) ((¬K ¬M) N) ложно. Ответ запишите в виде строки из четырех символов: значений переменных K, L, M и N (в указанном порядке). Так, например, строка 1101 соответствует тому, что K=1, L=1, M=0, N=1.



Вариант 4.

1. Какое логическое выражение эквивалентно выражению ¬(A ¬B ¬C)?

1) ¬A B C 2) ¬A B ¬C 3) ¬A B C 4) A B ¬C

2.Каково наименьшее натуральное число X, при котором высказывание

¬(X·X < 9) (X >(X + 2)) будет ложным?

3.Укажите значения логических переменных Р, Q, S, Т, при которых логическое выражение ¬Q) (Q (S Т)) ложно. Ответ запишите в виде строки из четырех символов: значений переменных Р, Q, S, T (в указанном порядке).



Вариант 5.

1. Какое логическое выражение эквивалентно выражению A ¬(B ¬ C)?

1) A ¬B C 2) A ¬B ¬C 3) A ¬B ¬C 4) A ¬B C

2.Каково наибольшее целое положительное число X, при котором ложно высказывание: (8·X - 6 < 75) (X·(X-1)> 65)

3.Укажите значения переменных K, L, M, N, при которых логическое выражение

(KM) (K ¬M) K (M ¬L N))

истинно. Ответ запишите в виде строки из четырех символов: значений переменных K, L, M и N (в указанном порядке). Так, например, строка 1101 соответствует тому, что K=1, L=1, M=0, N=1.



Вариант 6.

1. Какое логическое выражение эквивалентно выражению ¬(¬A B) C?

1) ¬A B ¬C 2) (A ¬B) C 3) (A B) C 4) A ¬B C

2.Каково наибольшее целое положительное число X, при котором ложно высказывание: (X·(X+1) > 55) (X·X > 50)

3.Сколько различных решений имеет уравнение J ¬K L ¬M (N ¬N) = 0

где J, K, L, M, N – логические переменные? В ответе не нужно перечислять все различные наборы значений J, K, L, M и N, при которых выполнено данное равенство. В качестве ответа вам нужно указать только количество таких наборов.



Вариант 7.

1. Какое логическое выражение эквивалентно выражению ¬(¬ A ¬ B) C?

1) ¬ A B ¬ C 2) (¬ A ¬ B) ¬C 3) (A B) C 4) A B C

2.Каково наибольшее целое положительное число X, при котором ложно высказывание: (9·X + 5 > 60) (X·X > 80)

3.Сколько различных решений имеет уравнение ¬M K ¬N ¬J (L ¬L) = 0

где J, K, L, M, N – логические переменные? В ответе не нужно перечислять все различные наборы значений J, K, L, M и N, при которых выполнено данное равенство. В качестве ответа вам нужно указать только количество таких наборов.



Вариант 8.

1. Какое логическое выражение равносильно выражению ¬ (A B) ¬C ?

1) ¬A B ¬C 2)(¬A ¬B) ¬C 3)(¬A ¬B) C 4) ¬A ¬B ¬C

2.Каково наибольшее целое положительное число X, при котором истинно высказывание: (X·(X+1) > X·X + 7) (X·(X+1)X·X + 7)

3.Сколько различных решений имеет уравнение (K L M) (¬L ¬M N) = 1

где K, L, M, N – логические переменные? В ответе не нужно перечислять все различные наборы значений K, L, M и N, при которых выполнено данное равенство. В качестве ответа вам нужно указать только количество таких наборов.



Вариант 9.

1. Какое логическое выражение эквивалентно выражению ¬(¬A B) ¬C?

1) (A B) ¬C 2) (A B) C 3) (A ¬B) ¬C 4) (A ¬B) ¬C

2.Каково наибольшее целое число X, при котором истинно высказывание:

(X·X - 1 > 100) (X·(X – 1) < 100)

3.Укажите значения переменных K, L, M, N, при которых логическое выражение

(K ¬M) L M K) ¬N

ложно. Ответ запишите в виде строки из четырех символов: значений переменных K, L, M и N (в указанном порядке). Так, например, строка 1101 соответствует тому, что K=1, L=1, M=0, N=1.



Вариант 10.

1. Какое логическое выражение эквивалентно выражению ¬(A B) ¬C?

1) (A B) ¬C 2) (A B) C 3) (¬A ¬B) ¬C 4) (A B) C

2.Каково наибольшее целое положительное число X, при котором истинно высказывание: (X·X - 7 > 15) (X·X + 8 < 35)

3.Сколько различных решений имеет уравнение (¬K ¬L ¬M) (L ¬M ¬N) = 0

где K, L, M, N – логические переменные? В ответе не нужно перечислять все различные наборы значений K, L, M и N, при которых выполнено данное равенство. В качестве ответа вам нужно указать только количество таких наборов.



Вариант 11.

1. Какое логическое выражение эквивалентно выражению ¬(A ¬B) ¬C?

1) A B C 2) ¬(A B) C 3) ¬(A C) B 4) ¬(A C) B

2.Сколько существует целых значений X, при которых ложно высказывание:

((X-4)·(X-6)0) (X·X - 12·X + 35 > 0)

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

((KL) (M ¬N) K) ¬(LM) = 1 где K, L, M, N – логические переменные? В ответе не нужно перечислять все различные наборы значений K, L, M и N, при которых выполнено данное равенство. В качестве ответа вам нужно указать только количество таких наборов.



Вариант 12.

1. Какое логическое выражение эквивалентно выражению A ¬(¬B ¬C)?

1) A B C 2) A B ¬C 3) A (B C) 4) (A ¬B) ¬C

2.Каково наибольшее целое положительное число X, при котором истинно высказывание: (X·(X + 1) > X·X + 7) (X·(X + 1) ≤ X·X + 7)

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

((J K) (M N)) ((J ¬K) (¬M ¬N)) (¬M ¬N K L)=1

где J, K, L, M, N – логические переменные? В ответе не нужно перечислять все различные наборы значений J, K, L, M и N, при которых выполнено данное равенство. В качестве ответа вам нужно указать только количество таких наборов.



Вариант 13.

1. Какое логическое выражение равносильно выражению ¬(А ¬B) ?

1) A B 2) A B 3) ¬A ¬B 4) ¬A B

2.Сколько существует целых значений X, при которых ложно высказывание:

¬((|X| < 5)  (|X| < 1)  (|X| < 10))

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

(JL) (KL) (M ¬N) (LM) (MK) = 1

где J, K, L, M, N – логические переменные? В ответе не нужно перечислять все различные наборы значений J, K, L, M и N, при которых выполнено данное равенство. В качестве ответа вам нужно указать только количество таких наборов.



Вариант 14.

1. Укажите, какое логическое выражение равносильно выражению ¬ (¬А B)?

1) A ¬B 2) ¬A B 3) B ¬A 4) A ¬B

2.Каково наибольшее натуральное число X, при котором истинно высказывание:

(X·(X + 1) > 99) (X·X < 65)

3.Укажите значения переменных K, L, M, N, при которых логическое выражение

(¬(M L) K) ((¬K ¬M) N)

ложно. Ответ запишите в виде строки из четырех символов: значений переменных K, L, M и N (в указанном порядке). Так, например, строка 1101 соответствует тому, что K=1, L=1, M=0, N=1.




1   2   3   4   5   6   7   8   9   10

Похожие:

Логика. Преобразование логических выражений Что нужно знать iconПреобразование логических выражений
«НЕ», затем – «или», потом – «импликация», и самая последняя – «эквиваленция»
Логика. Преобразование логических выражений Что нужно знать iconЭкзамен по спецкурсу и спецсеминару Математическая логика
Математическая логика. Высказывания. Таблицы истинности. Основные логические операции, их свойства. Упрощение логических выражений....
Логика. Преобразование логических выражений Что нужно знать iconПостроение таблиц истинности логических выражений
Символом f обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения...
Логика. Преобразование логических выражений Что нужно знать iconПреобразование логических выражений. Формулы де Моргана
«НЕ» для сложного выражения в скобках, которую раскрываем по формуле де Моргана
Логика. Преобразование логических выражений Что нужно знать iconЛогика компьютера
Математическая логика изучает вопросы применения математических методов для решения логических задач и построения логических схем....
Логика. Преобразование логических выражений Что нужно знать iconПреобразование тригонометрических выражений
Выполняя упрощение выражений использовали тригонометрические тождества и формулы сокращенного умножения
Логика. Преобразование логических выражений Что нужно знать iconПреобразование логических выражений
Автор, к своему стыду, до сих пор иногда путает  и . Поэтому на его уроках операция «НЕ» обозначается чертой сверху, «И» – знаком...
Логика. Преобразование логических выражений Что нужно знать iconПреобразование логических выражений
Автор, к своему стыду, до сих пор иногда путает  и . Поэтому на его уроках операция «НЕ» обозначается чертой сверху, «И» – знаком...
Логика. Преобразование логических выражений Что нужно знать icon"Преобразование выражений, содержащих степени с дробными показателями"
Разработка урока по алгебре в 9классе на тему: “Преобразование выражений, содержащих степени с дробными показателями”
Логика. Преобразование логических выражений Что нужно знать iconИ1 Планирование информационного поиска
Вы дома делаете ремонт. Нужно посчитать, сколько денег нужно отложить на покупку обоев в твою комнату. Что тебе нужно знать, чтобы...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org