Решение систем логических уравнений

Задание 23 ЕГЭ по информатике.

По мнению составителей ЕГЭ, задание на решение системы логических уравнений остается одним из самых сложных, относится к высокому уровню сложности, хотя за него дают 1 балл. Это задание незаслуженно находится в первой части, так как оно не только проверяет знание логических операций, но и учит рассуждать, строить логические цепочки. При оценке ответа нет возможности квалифицировать ошибку, так как ответ, как и логическое высказывание, бывает либо истинным, либо ложным. А поводов дать неверный в этом случае ответ много: можно написать наугад, а можно решить все от от начала до конца, проделать все логические преобразования, выстроить верную цепочку рассуждений и в последнем действии допустить арифметическую ошибку.

Найти число решений системы логических уравнений. Необходимо описать все(!) уравнения системы. Переменные могут состоять из любого количества латинских символов и цифр и начинаются с латинской буквы. Каждое уравнение задается на новой строке. Для задания операций используйте следующие символы (пробелы игнорируются):

    * Операция конъюнкции (логическое умножение — "И")

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

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

Сколь­ко су­ще­ству­ет раз­лич­ных на­бо­ров зна­че­ний ло­ги­че­ских пе­ре­мен­ных x1, х2, х3, х4, х5, х6, х7, х8, ко­то­рые удо­вле­тво­ря­ют всем пе­ре­чис­лен­ным ниже усло­ви­ям?

(x1 → х2) → (х3→ х4) = 1

(х3 → х4) → (х5 → х6) = 1

(х5 → х6) → (х7 → х8) = 1

В от­ве­те не нужно пе­ре­чис­лять все раз­лич­ные на­бо­ры зна­че­ний пе­ре­мен­ных x1, х2, х3, х4, х5, х6, х7, х8, при ко­то­рых вы­пол­не­на дан­ная си­сте­ма ра­венств. В ка­че­стве от­ве­та Вам нужно ука­зать ко­ли­че­ство таких на­бо­ров.

Сде­ла­ем за­ме­ну пе­ре­мен­ных:

(x1 → х2) = y1; (х3 → х4) = y2; (х5 → х6) = y3; (х7 → х8) = y4.

Тогда можно за­пи­сать си­сте­му в виде од­но­го урав­не­ния:

(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) = 1. Конъюнкция равна 1 (истинна), когда каждый операнд принимает значение 1. Т.е. каждая из импликаций должна быть истинна, а это выполняется при всех значениях, кроме (1 → 0). Т.е. в таблице значений переменных y1, y2, y3, y4 единица не должна стоять левее нуля:

Т.е. условия выполняются для 5 наборов y1-y4.

Т.к. y1 = x1 → x2, то значение y1 = 0 достигается на единственном наборе x1, x2: (1, 0), а значение y1 = 1 – на трех наборах x1, x2: (0,0) , (0,1), (1,1). Аналогично для y2, y3, y4.

Поскольку каждый набор (x1,x2) для переменной y1 сочетается с каждым набором (x3,x4) для переменной y2 и т.д., то количества наборов переменных x перемножаются:

Кол-во наборов на x1…x8

Сло­жим ко­ли­че­ство наборов: 1 + 3 + 9 + 27 + 81 = 121.

Сколько существует различных наборов значений логических переменных x1, x2, . x9, y1, y2, . y9, которые удовлетворяют всем перечисленным ниже условиям?

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

Читайте также  Протокол both что это

Сде­ла­ем за­ме­ну пе­ре­мен­ных:

(x1 ≡ y1) = z1, (x2 ≡ y2) = z2,…. ,(x9 ≡ y9) = z9

Систему можно записать в виде одного уравнения:

(¬ z1 ≡ z2) ∧ (¬ z2 ≡ z3) ∧ …..∧ (¬ z8 ≡ z9)

Эквивалентность истинна, только если оба операнда равны. Решениями этого уравнения будут два набора:

z1 z2 z3 z4 z5 z6 z7 z8 z9
1 1 1 1
1 1 1 1 1

Т.к. zi = (xi ≡ yi), то значению zi = 0 соответствуют два набора (xi,yi): (0,1) и (1,0), а значению zi = 1 — два набора (xi,yi): (0,0) и (1,1).

Тогда первому набору z1, z2,…, z9 соответствует 2 9 наборов (x1,y1), (x2,y2),…, (x9,y9).

Столько же соответствует второму набору z1, z2,…, z9. Тогда всего 2 9 +2 9 = 1024 наборов.

Решение систем логических уравнений методом визуального определения рекурсии.

Этот метод применяется, если система уравнений достаточно проста и порядок увеличения количества наборов при добавлении переменных очевиден.

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

где x1, x2, … x10 — ло­ги­че­ские пе­ре­мен­ные?

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

Решим первое уравнение. Дизъюнкция равна 1, если хотя бы один из ее операндов равен 1. Т.е. решениями являются наборы:

Для x1=0 существуют два значения x2 ( 0 и 1), а для x1=1 только одно значение x2 (1), такие, что набор (x1,x2) является решением уравнения. Всего 3 набора.

Добавим переменную x3 и рассмотрим второе уравнение. Оно аналогично первому, значит для x2=0 существуют два значения x3 ( 0 и 1), а для x2=1 только одно значение x3 (1), такие, что набор (x2,x3) является решением уравнения. Всего 4 набора.

Несложно заметить, что при добавлении очередной переменной добавляется один набор. Т.е. рекурсивная формула количества наборов на (i+1) переменных:

Ni+1 = Ni + 1. Тогда для десяти переменных получим 11 наборов.

Решение систем логических уравнений различного типа

Сколь­ко су­ще­ству­ет раз­лич­ных на­бо­ров зна­че­ний ло­ги­че­ских пе­ре­мен­ных x1, . x4, y1. y4, z1. z4, ко­то­рые удо­вле­тво­ря­ют всем пе­ре­чис­лен­ным ниже усло­ви­ям?

В от­ве­те не нужно пе­ре­чис­лять все раз­лич­ные на­бо­ры зна­че­ний пе­ре­мен­ных x1, . x4, y1, . y4, z1, . z4, при ко­то­рых вы­пол­не­на дан­ная си­сте­ма ра­венств.

В ка­че­стве от­ве­та Вам нужно ука­зать ко­ли­че­ство таких на­бо­ров.

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

Рассмотрим первое уравнение. Конъюнкция истинна (равна 1) только тогда, когда все ее операнды истинны (равны 1). Импликация равна 1 на всех наборах, кроме (1,0). Значит, решением первого уравнения будут такие наборы x1, x2, x3, x4, в которых 1 не стоит левее 0 (5 наборов):

Аналогично, решениями второго и третьего уравнений будут абсолютно такие же наборы y1,…,y4 и z1,…, z4.

Теперь проанализируем четвертое уравнение системы: x4 ∧ y4 ∧ z4 = 0. Решением будут все наборы x4, y4, z4, в которых хотя бы одна из переменных равна 0.

Т.е. для x4 = 0 подойдут все возможные наборы (y4, z4), а для x4 = 1 подойдут наборы (y4, z4), в которых присутствует хотя бы один ноль : (0, 0), (0,1) , (1,0).

Общее количество наборов 25 + 4*9 = 25 + 36 = 61.

Решение систем логических уравнений методом построения рекуррентных формул

Метод построения рекуррентных формул применяется при решении сложных систем, в которых порядок увеличения количества наборов неочевиден, а построение дерева невозможно из-за объемов.

Читайте также  Программа со всеми драйверами для виндовс 7

Сколь­ко су­ще­ству­ет раз­лич­ных на­бо­ров зна­че­ний ло­ги­че­ских пе­ре­мен­ных x1, x2, … x7, y1, y2, … y7, ко­то­рые удо­вле­тво­ря­ют всем пе­ре­чис­лен­ным ниже усло­ви­ям?

(x1 ∨ y1) ∧ ((x2 ∧ y2) → (x1 ∧ y1)) = 1

(x2 ∨ y2) ∧ ((x3 ∧ y3) → (x2 ∧ y2)) = 1

(x6 ∨ y6) ∧ ((x7 ∧ y7) → (x6 ∧ y6)) = 1

В от­ве­те не нужно пе­ре­чис­лять все раз­лич­ные на­бо­ры зна­че­ний пе­ре­мен­ных x1, x2, . x7, y1, y2, . y7, при ко­то­рых вы­пол­не­на дан­ная си­сте­ма ра­венств. В ка­че­стве от­ве­та Вам нужно ука­зать ко­ли­че­ство таких на­бо­ров.

Заметим, что первые шесть уравнений системы одинаковы и отличаются только набором переменных. Рассмотрим первое уравнение. Его решением будут следующие наборы переменных:

число наборов (0,0) на переменных (x1,y1) через A1,

число наборов (0,1) на переменных (x1,y1) через B1,

число наборов (1,0) на переменных (x1,y1) через C1,

число наборов (1,1) на переменных (x1,y1) через D1.

число наборов (0,0) на переменных (x2,y2) через A2,

число наборов (0,1) на переменных (x2,y2) через B2,

число наборов (1,0) на переменных (x2,y2) через C2,

число наборов (1,1) на переменных (x2,y2) через D2.

Из дерева решений видим, что

Заметим, что набор (0,0) на переменных (x2,y2) получается из наборов (0,1), (1,0) и (1,1) на переменных (x1,y1). Т.е. A2=B1+C1+D1.

Набор (0,1) на переменных (x2,y2) получается из наборов (0,1), (1,0) и (1,1) на переменных (x1,y1). Т.е. B2=B1+C1+D1.

Таким образом, получаем рекуррентные формулы:

Наборы Обозн. Формула

Количество наборов

i=1 i=2 i=3 i=4 i=5 i=6 i=7 (0,0) Ai Ai+1=Bi+Ci+Di 3 7 15 31 63 127 (0,1) Bi Bi+1=Bi+Ci+Di 1 3 7 15 31 63 127 (1,0) Ci Ci+1=Bi+Ci+Di 1 3 7 15 31 63 127 (1,1) Di Di+1=Di 1 1 1 1 1 1 1

Последнему уравнению (x7 ∨ y7) = 1 удовлетворяют все наборы, кроме тех, в которых x7=0 и y7=0. В нашей таблице число таких наборов A7.

Тогда общее количество наборов равно B7 + C7 + D7 = 127+127+1 = 255

Ты нашел то, что искал? Поделись с друзьями!

Звоните нам: 8 (800) 775-06-82 (бесплатный звонок по России) +7 (495) 984-09-27 (бесплатный звонок по Москве)

Или нажмите на кнопку «Узнать больше», чтобы заполнить контактную форму. Мы обязательно Вам перезвоним.

Обучающее видео
БЕСПЛАТНО

Техническая поддержка:
help@ege-study.ru (круглосуточно)

Полный онлайн-курс подготовки к ЕГЭ по математике. Структурировано. Четко. Без воды. Сдай ЕГЭ на 100 баллов!

Для нормального функционирования и Вашего удобства, сайт использует файлы cookies. Это совершенно обычная практика.Продолжая использовать портал, Вы соглашаетесь с нашей Политикой конфиденциальности.

Все поля обязательны для заполнения

Премиум

Вся часть 2 на ЕГЭ по математике, от задачи 13 до задачи 19. То, о чем не рассказывают даже ваши репетиторы. Все приемы решения задач части 2. Оформление задач на экзамене. Десятки реальных задач ЕГЭ, от простых до самых сложных.

Видеокурс «Премиум» состоит из 7 курсов для освоения части 2 ЕГЭ по математике (задачи 13-19). Длительность каждого курса — от 3,5 до 4,5 часов.

  1. Уравнения (задача 13)
  2. Стереометрия (задача 14)
  3. Неравенства (задача 15)
  4. Геометрия (задача 16)
  5. Финансовая математика (задача 17)
  6. Параметры (задача 18)
  7. Нестандартная задача на числа и их свойства (задача 19).
Читайте также  Сколько хранятся телефонные разговоры у операторов

Здесь то, чего нет в учебниках. Чего вам не расскажут в школе. Приемы, методы и секреты решения задач части 2.

Каждая тема разобрана с нуля. Десятки специально подобранных задач, каждая из которых помогает понять «подводные камни» и хитрости решения. Автор видеокурса Премиум — репетитор-профессионал Анна Малкова.

Получи пятерку

Видеокурс «Получи пятерку» включает все темы, необходимые для успешной сдачи ЕГЭ по математике на 60-65 баллов. Полностью все задачи 1-13 Профильного ЕГЭ по математике. Подходит также для сдачи Базового ЕГЭ по математике. Если вы хотите сдать ЕГЭ на 90-100 баллов, вам надо решать часть 1 за 30 минут и без ошибок!

Курс подготовки к ЕГЭ для 10-11 класса, а также для преподавателей. Все необходимое, чтобы решить часть 1 ЕГЭ по математике (первые 12 задач) и задачу 13 (тригонометрия). А это более 70 баллов на ЕГЭ, и без них не обойтись ни стобалльнику, ни гуманитарию.

Вся необходимая теория. Быстрые способы решения, ловушки и секреты ЕГЭ. Разобраны все актуальные задания части 1 из Банка заданий ФИПИ. Курс полностью соответствует требованиям ЕГЭ-2018.

Курс содержит 5 больших тем, по 2,5 часа каждая. Каждая тема дается с нуля, просто и понятно.

Сотни заданий ЕГЭ. Текстовые задачи и теория вероятностей. Простые и легко запоминаемые алгоритмы решения задач. Геометрия. Теория, справочный материал, разбор всех типов заданий ЕГЭ. Стереометрия. Хитрые приемы решения, полезные шпаргалки, развитие пространственного воображения. Тригонометрия с нуля — до задачи 13. Понимание вместо зубрежки. Наглядное объяснение сложных понятий. Алгебра. Корни, степени и логарифмы, функция и производная. База для решения сложных задач 2 части ЕГЭ.

Сразу после оплаты вы получите ссылки на скачивание видеокурсов и уникальные ключи к ним.

Задачи комплекта «Математические тренинги — 2019» непростые. В каждой – интересные хитрости, «подводные камни», полезные секреты.

Варианты составлены так, чтобы охватить все возможные сложные задачи, как первой, так и второй части ЕГЭ по математике.

Как пользоваться?

  1. Не надо сразу просматривать задачи (и решения) всех вариантов. Такое читерство вам только помешает. Берите по одному! Задачи решайте по однойи старайтесь довести до ответа.
  2. Если почти ничего не получилось – начинать надо не с решения вариантов, а с изучения математики. Вам помогут книга для подготовки к ЕГЭи Годовой Онлайн-курс.
  3. Если вы правильно решили из первого варианта Маттренингов 5-7 задач – значит, знаний не хватает. Смотри пункт 1: Книгаи Годовой Онлайн-курс!
  4. Обязательно разберите правильные решения. Посмотрите видеоразбор – в нем тоже много полезного.
  5. Можно решать самостоятельно или вместе с друзьями. Или всем классом. А потом смотреть видеоразбор варианта.

Стоимость комплекта «Математические тренинги – 2019» — всего 1100 рублей. За 5 вариантов с решениями и видеоразбором каждого.

Это пробная версия онлайн курса по профильной математике.

Вы получите доступ к 3 темам, которые помогут понять принцип обучения, работу платформы и оценить ведущую курса Анну Малкову.

— 3 темы курса (из 50).
— Текстовый учебник с видеопримерами.
— Мастер-класс Анны Малковой.
— Тренажер для отработки задач.

Регистрируйтесь, это бесплатно!

Нажимая на кнопку, вы даете согласие на обработку своих персональных данных

Ссылка на основную публикацию
Adblock
detector