По завершению года оказалось, что только одно из трех предположений истинно. Какие подразделения получили по итогам года прибыль?

Решение. Запишем предположения из условия задачи в виде логических высказываний: «Получение прибыли подразделением B не является необходимым условием для получения

прибыли подразделением A »: F 1 (A , B , C ) = A → B

«Получение прибыли хотя бы одним подразделений B и C не является достаточным для получения прибыли подразделением A »: F 2 (A , B , C ) = (B + C ) → A

«Подразделения A и B не получат прибыль одновременно»: F 3 (A , B , C ) = A B

Из условия известно, что только одно из трех предположений истинно. Это значит, что мы должны найти какое из трех следующих логических выражений не является тождественно ложным:

1) F 1 F 2 F 3

2) F 1 F 2 F 3

3) F 1 F 2 F 3

1) (A → B) ((B + C) → A) (A ↔ B) = A B (B C + A) (A B + A B) = 0

2) (A → B) ((B + C) → A) (A ↔ B) = (A + B) (A B + A C) (A B + A B) = A B C

3) (A → B) ((B + C) → A) (A B) = (A + B) (B C + A) (A B + A B) = 0

Следовательно, по итогам годы истинным оказалось второе предположение, а первое и третье – ложными.

									A = 0
	F1 F2 F3 = A B C = 1
									в том и только в том случае, когда B = 0 .
									C = 1

Следовательно, что прибыль получит подразделение C , а подразделения A и B прибыль не получат.

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

В текстах государственного централизованного тестирования есть задание (А8), в котором предлагается найти корень логического уравнения. Давайте разберем способы решения подобных заданий на примере.

Найти корень логического уравнения: (A + B )(X AB ) = B + X → A .

Первый способ решения – построение таблицы истинности. Построим таблицы истинности правой и левой части уравнения и посмотрим, при каком X , значения в последних столбцах этих таблиц совпадут.

F1 (A, B, X ) = (A + B)(X AB)

					A + B	(A + B)(X AB)	F 1 (A , B , X )

F2 (A, B, X ) = B + X → A

			X → A							F 2 (A , B , X )
					X → A			X → A

Сравним полученные таблицы истинности и выберем те строки, в которых значения F 1 (A , B , X ) и F 2 (A , B , X ) совпадают.

			F 1 (A , B , X )	F 2 (A , B , X )

Перепишем только выбранные строки, оставив только столбцы аргументов. Посмотрим на переменную X как на функцию от A и B .

Очевидно, что X = B → A .

Второй способ решения – заменить знак равенства в уравнении на знак эквиваленции, а затем упростить полученное логическое уравнение.

Для облегчения дальнейшей работы предварительно упростим правую и левую части логического уравнения и найдем их отрицания:

F1 = (A + B)(X AB) = A + B + (X ↔ AB) = A B + X A B + X A + X B

F1 = (A + B)(X AB) = (A + B)(X A + X B + X A B) = X A B + X A B + X A B

F2 = B + X → A = B (X → A) = B (X + A) = X B + A B F2 = B + X → A = B + X + A = B + X A

Заменим в нашем логическом уравнении знак равенства на знак эквивалентности:

F1 ↔ F2 = F1 F2 + F1 F2 = (A B + X A B + X A + X B) (X B + A B) +

+ (X A B + X A B + X A B) (B + X A) =

= (X A B + X B + X A B) + (X A B + X A B) =

Перегруппируем логические слагаемые данного выражения, вынеся за скобку множители X и X .

X (A B) + X (B + AB) = X (A B) + X (B + A) =

Обозначим T = A B , тогда

X T + X T = X ↔ T .

Следовательно, чтобы логическое уравнение имеет решение: X = A B = B + A = B → A .

Логические элементы ЭВМ. Построение функциональных схем

Математическая логика с развитием ВТ оказалась в тесной взаимосвязи с вопросами конструирования и программирования вычислительной техники. Алгебра логики нашла широкое применение первоначально при разработке релейно-контактных схем . Первым фундаментальным исследованием, обратившим внимание инженеров, занимавшихся проектированием ЭВМ, на возможность анализа электрических цепей с помощью булевой алгебры была опубликована в декабре 1938 года статья американца Клода Шеннона «Символический анализ релейно-контактных схем». После этой статьи проектирование ЭВМ не обходилось без применения булевой алгебры.

Логический элемент - это схема, реализующая логические операции дизъюнкции, конъюнкции и инверсии. Рассмотрим реализацию логических элементов через электрические релейно-контактные схемы, знакомые вам из школьного курса физики.

Последовательное соединение контактов

Параллельное соединение контактов

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

		Состояние цепи с	Состояние цепи с параллельным
		последовательным соединением	соединением

Как видно, цепь с последовательным соединением соответствует логической операции конъюнкция, так как ток в цепи появляется только при одновременном замыкании контактов A и B . Цепь с параллельным соединением соответствует логической операции дизъюнкция, так как ток в цепи отсутствует только в момент, когда оба контакта разомкнуты.

Логическая операция инверсии реализуется через контактную схему электромагнитного реле, принцип которого изучается в школьном курсе физики. Контакт x разомкнут, когда x замкнут, и наоборот.

Использование релейно-контактных элементов для построения логических схем вычислительных машин не оправдало себя ввиду низкой надежности, больших габаритов, большого энергопотребления и низкого быстродействия. Появление электронных приборов (вакуумных и полупроводниковых) создало возможность построения логических элементов с быстродействием от 1 миллиона переключений в секунду и выше. Логические элементы на полупроводниках работают в режиме ключа аналогично электромагнитному реле. Вся теория, изложенная для контактных схем, переносится на полупроводниковые элементы. Логические элементы на полупроводниках характеризуются не состоянием контактов, а наличием сигналов на входе и выходе.

Рассмотрим логические элементы, реализующие основные логические операции:

Инвертор - реализует операцию отрицания или инверсию. У

инвертора один вход и один выход. Сигнал на выходе появляется

тогда, когда на входе его нет, и наоборот.

Конъюнктор -

X1 X 2 ... X n

реализует операцию конъюнкции.

У конъюнктора

один выход и не менее двух входов. Сигнал на

выходе появляется тогда и только тогда, когда на

все входы поданы сигналы.

X 2 + ... X n

Дизъюнктор - реализует операцию дизъюнкции. У

дизъюнктора один выход и не менее двух

Сигнал на выходе не появляется тогда и только тогда,

когда на все входы не поданы сигналы.

	Построить	функциональную
F(X , Y, Z) = X (Y + Z)
			X + Z

схему, соответствующую функции:

& F(X , Y , Z )

Решение задач с использованием конъюнктивно-нормальной

и дизъюнктивно-нормальной форм

В задачниках по логике часто встречаются стандартные задачи, где нужно записать функцию, реализующую релейно-контактную схему, упростить ее и построить таблицу истинности для этой функции. А как решать обратную задачу? Дана произвольная таблица истинности, нужно построить функциональную или релейно-контактную схему. Этим вопросом мы и займемся сегодня.

Любую функцию алгебры логики можно представить комбинацией трех операций: конъюнкции, дизъюнкции и инверсии. Давайте разберемся, как это делается. Для этого запишем несколько определений.

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

аргументов, и значение 0 при всех остальных. Пример: x 1 x 2 x 3 x 4 .

Макстерм - это функция, образованная дизъюнкцией некоторого числа переменных или их отрицаний. Макстерм принимает значение 0 в одном из возможных наборов, и 1 при всех других.

Пример: x 1 + x 2 + x 3 .

Функция в дизъюнктивной нормальной форме (ДНФ) является логической суммой минтермов.

Пример: x 1 x 2 + x 1 x 2 + x 1 x 2 x 3 .

Конъюнктивная нормальная форма (КНФ) является логическим произведением элементарных дизъюнкций (макстермов).

Пример: (x 1 + x 2 + x 3 ) (x 1 + x 2 ) .

Совершенной дизъюнктивно-нормальной формой называется ДНФ, в каждом минтерме которой присутствуют все переменные или их отрицания.

Пример: x 1 x 2 x 3 + x 1 x 2 x 3 + x 1 x 2 x 3

Совершенной конъюктивно-нормальной формой называется КНФ, в каждом макстерме которой присутствуют все переменные или их отрицания.

Пример: (x 1 + x 2 + x 3 ) (x 1 + x 2 + x 3 )

Запись логической функции по таблице

Любая логическая функция может быть выражена в виде СДНФ или СКНФ. В качестве примера рассмотрим функцию f , представленную в таблице.

			f(x1 , x2 , x3 )

Функции G0, G1, G4, G5, G7 – это минтермы (см. определение). Каждая из этих функций является произведением трех переменных или их инверсий и принимает значение 1 только в одной ситуации. Видно, что для того, чтобы получить 1 в значении функции f, нужен один минтерм. Следовательно, количество минтермов, составляющих СДНФ этой функции, равно количеству единиц в значении функции: f= G0+G1+G4+G5+G7. Таким образом, СДНФ имеет вид:

f (x 1, x 2 , x 3 ) = x 1 x 2 x 3 + x 1 x 2 x 3 + x 1 x 2 x 3 + x 1 x 2 x 3 + x 1 x 2 x 3.

Аналогично можно построить СКНФ. Количество сомножителей равно количеству нулей в значениях функции:

f (x 1, x 2 , x 3 ) = (x 1 + x 2 + x 3 ) (x 1 + x 2 + x 3 ) (x 1 + x 2 + x 3 ) .

Таким образом, можно записать в виде формулы любую логическую функцию, заданную в виде таблицы.

Алгоритм построения СДНФ по таблице истинности

Дана таблица истинности некоторой функции. Для построения СДНФ необходимо выполнить следующую последовательность шагов:

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

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

3. Наконец, образуем дизъюнкцию всех полученных минтермов. Количество минтермов должно совпадать с количеством единиц логической функции.

Алгоритм построения СКНФ по таблице истинности

Дана таблица истинности некоторой функции. Для построения СКНФ необходимо выполнить следующую последовательность шагов:

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

2. Каждой такой строке поставить в соответствие дизъюнкцию всех аргументов или их инверсий (макстерм). При этом аргумент, принимающий значение 1, входит в макстерм с отрицанием, а значение 1 – без отрицания.

3. Наконец, образуем конъюнкцию всех полученных макстермов. Количество макстермов должно совпадать с количеством нулей логической функции.

Если условиться из двух форм (СДНФ или СКНФ) отдавать предпочтение той, которая содержит меньше букв, то СДНФ предпочтительней, если среди значений функции таблицы истинности меньше единиц, СКНФ – если меньше нулей.

Пример. Дана таблица истинности логической функции от трех переменных. Построить логическую формулу, реализующую эту функцию.

			F(A, B, C)

Выберем те строки в данной таблице истинности, в которых значения функции равна 0.

F(A, B, C) = (A + B + C) (A + B + C)

Проверим выведенную функцию, составив таблицу истинности.

Сравнив начальную и итоговую таблицу истинности можно сделать вывод, что логическая функция построена правильно.

Решение задач

1. Три преподавателя отбирают задачи для олимпиады. На выбор предлагается несколько задач. По каждой задаче каждый из преподавателей высказывает свое мнение: легкая (0) или трудная (1) задача. Задача включается в олимпиадное задание, если не менее двух преподавателей отметили ее как трудную, но если все три преподавателя считают ее трудной, то такая задача не включается в олимпиадное задание как слишком сложная. Составьте логическую схему устройства, которое будет выдавать на выходе 1, если задача включается в олимпиадное задание, и 0, если не включается.

Построим таблицу истинности искомой функции. У нас есть три входные переменные (три преподавателя). Следовательно, искомая функция будет функцией от трех переменных.

Анализируя условие задачи, получаем следующую таблицу истинности:

Строим СДНФ. F(A, B, C) = ABC + ABC + ABC

Теперь строим логическую схему этой функции.

B & 1 F(A,B,C)

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

Итак, у нас есть три выключателя, которыми мы должны включать и выключать свет. У каждого выключателя есть два состояния: верхнее (0) и нижнее (1). Предположим, что если все три выключателя в положении 0, свет в подъезде выключен. Тогда при переводе любого из трех выключателей в положение 1 свет в подъезде должен загореться. Очевидно, что при переводе любого другого выключателя в положение 1, свет в подъезде выключится. Если третий выключатель перевести в положение 1, свет в подъезде загорится. Строим таблицу истинности.

Тогда, F(A, B, C) = ABC + ABC + ABC + ABC .

	3. Условие изменения			значения логической функции			F(A, B, C) = C →		A + B
	одновременном изменении аргументов B и C равно:
		A → (B C)						(B C) → A
					A(B C)
	4) (B C) → A				A → (B C)

Примечание. Для успешного решения данной задачи вспомним следующие логические формулы:

x → y = x + y x y = x y + x y

x ↔ y = x y + x y

Нам дана логическая функция от трех переменных F 1 (A , B , C ) = C → A + B = C + A B .

Изменим одновременно переменные B и C : F 2 (A , B , C ) = F 1 (A , B , C ) = C + A B . Построим таблицы истинности этих двух функций:

Анализируем полученную таблицу. Из восьми строк таблицы лишь в двух (2-й и 3-й) функция не изменяет своего значения. Обратите внимание, что в этих строках переменная A не изменяет своего значения на противоположное, а переменные B и C – изменяют.

Строим СКНФ функции по этим строкам:

F3 (A, B, C) = (A + B + C) (A + B C) = A + AB + AC + AB + BC + AC + B C = .

A + (B ↔ C) = A + B C = (B C) → A

Следовательно, искомый ответ – 4.

4. Условие изменения значения логической функции F (A , B , C ) = C + AB при одновременном изменении аргументов A и B равно:

1) C + (A B)

C + (A B)

C(A B)

4) C(A B)

C → (A B)

F 1 (A , B ,C ) =

C + AB

F 2 (A , B ,C ) = F 1 (

C ) = A

Строим таблицу истинности.

Анализируем полученную таблицу. Из восьми строк таблицы лишь в двух (1-й и 7-й) функция меняет свое значение. Обратите внимание, что в этих строках переменная С не меняет свое значение, а переменные A и B – меняют.

Строим СДНФ функции по этим строкам:

F3 (A, B, C) = A B C + A B C = C(A B + A B) = C(A ↔ B) = C + (A B)

Следовательно, искомый ответ – 2.

Использованная литература

1. Шапиро С.И. Решение логических и игровых задач (логико-психологические этюды). – М.: Радио и связь, 1984. – 152 с.

2. Шоломов Л.А. Основы теории дискретных логических и вычислительных устройств. – М.: Наука. Гл. ред. физ. - мат. лит., 1980. - 400 с.

3. Пухальский Г.И., Новосельцева Т.Я. Проектирование дискретных устройств на интегральных микросхемах.: Справочник. – М.: Радио и связь, 1990.

Муниципальное бюджетное общеобразовательное учреждение

«Средняя общеобразовательная школа № 18»

городского округа город Салават Республики Башкортостан

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

в задачах ЕГЭ по информатике

Раздел «Основы алгебры логики» в заданиях ЕГЭ считается одним из самых сложных и плохо решаемых. Средний процент выполнения заданий по данной теме самый низкий и составляет 43,2.

Раздел курса	Средний процент выполнения по группам заданий
Кодирование информации и измерение ее количества
Информационное моделирование
Системы счисления
Основы алгебры логики
Алгоритмизация и программирование
Основы информационно- коммуникационных технологий

Исходя из спецификации КИМа 2018 года этот блок включает четыре задания разного уровня сложности.

№ задания	Проверяемые элементы содержания	Уровень сложности задания
	Умение строить таблицы истинности и логические схемы
	Умение осуществлять поиск информации в сети Интернет
	Знание основных понятий и законов математической логики
	Умение строить и преобразовывать логические выражения

Задание 23 является высоким по уровню сложности, поэтому имеет самый низкий процент выполнения. Среди подготовленных выпускников (81-100 баллов) 49,8% выполнивших, средне подготовленные (61-80 баллов) справляются на 13,7%, оставшаяся группа учеников данное задание не выполняет.

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

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

(23.154 Поляков К.Ю.) Сколько различных решений имеет система уравнений?

((x 1  y 1 )  (x 2  y 2 ))  (x 1  x 2 )  (y 1  y 2 ) =1

((x 2  y 2 )  (x 3  y 3 ))  (x 2  x 3 )  (y 2  y 3 ) =1

((x 7  y 7 )  (x 8  y 8 ))  (x 7  x 8 )  (y 7  y 8 ) =1

где x 1 , x 2 ,…, x 8, у 1 ,у 2 ,…,у 8 - логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.

Решение . Все уравнения, включенные в систему, однотипны, и в каждое уравнение включено четыре переменных. Зная x1 и y1, можем найти все возможные значения x2 и y2, удовлетворяющие первому уравнению. Рассуждая аналогичным образом, из известных x2 и y2можем найти x3, y3, удовлетворяющее второму уравнению. То есть, зная пару (x1 , y1) и определив значение пары (x2 , y2) , мы найдем пару (x3 , y3 ), которая, в свою очередь, приведет к паре (x4 , y4 ) и так далее.

Найдем все решения первого уравнения. Это можно сделать двумя способами: построить таблицу истинности, через рассуждения и применение законов логики.

Таблица истинности:

				x 1  y 1	x 2  y 2	(x 1  y 1 )  (x 2  y 2 )	(x 1  x 2 )	(y 1  y 2 )	(x 1  x 2 )  (y 1  y 2 )

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

(x 1  y 1 )  (x 2  y 2 ))=1

(x 1  x 2 ) =1

(y 1  y 2 ) =1

Рассмотрим первое уравнение. Следование равно 1, когда 0 0, 0 1, 1 1, значит (x1 y1)=0 при (01), (10), то пара (x 2  y 2 ) может быть любой (00), (01), (10), (11), а при (x1 y1)=1, то есть (00) и (11) пара (x2 y2)=1 принимает такие же значения (00) и (11). Исключим из этого решения те пары, для которых ложны второе и третье уравнения, то есть x1=1, x2=0, y1=1, y2=0.

(x 1 , y 1 )	(x 2 , y 2 )

Общее количество пар 1+1+1+22=25

2) (23.160 Поляков К.Ю.) Сколько различных решений имеет система логических уравнений

(x 1  (x 2  y 2 ))  (y 1  y 2 ) = 1

(x 2  (x 3  y 3 ))  (y 2  y 3 ) = 1

...

( x 6  ( x 7  y 7 ))  ( y 6  y 7 ) = 1

x 7  y 7 = 1

Решение. 1) Уравнения однотипные, поэтому методом рассуждения найдем всевозможные пары (x1,y1), (x2,y2) первого уравнения.

(x 1  (x 2  y 2 ))=1

(y 1  y 2 ) = 1

Решением второго уравнения являются пары (00), (01), (11).

Найдем решения первого уравнения. Если x1=0, то x2 , y2 - любые, если x1=1, то x2 , y2 принимает значение (11).

Составим связи между парами (x1 , y1) и (x2 , y2).

(x 1 , y 1 )	(x 2 , y 2 )

Составим таблицу для вычисления количества пар на каждом этапе.

							0

Учитывая решения последнего уравнения x 7  y 7 = 1, исключим пару (10). Находим общее число решений 1+7+0+34=42

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

(x 1  x 2 )  (x 3  x 4 ) = 1

(x 3  x 4 )  (x 5  x 6 ) = 1

(x 5  x 6 )  (x 7  x 8 ) = 1

(x 7  x 8 )  (x 9  x 10 ) = 1

x 1  x 3  x 5  x 7  x 9 = 1

Решение. 1) Уравнения однотипные, поэтому методом рассуждения найдем всевозможные пары (x1,x2), (x3,x4) первого уравнения.

(x 1  x 2 )  (x 3  x 4 ) = 1

Исключим из решения пары, которые в следовании дают 0 (1 0), это пары (01, 00, 11) и (10).

Составим связи между парами (x1,x2), (x3,x4)

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

Данная методика основана на использование таблиц истинности, рассчитана на учащихся, которые владеют методами преобразования логических выражений. Если учащиеся плохо владеют этими методами, можно использовать и без преобразований. (Мы будем использовать преобразования). Для овладения этим способом решения, необходимы в обязательном порядке знание свойств основных логических операций: конъюнкции, дизъюнкции, инверсии, импликации и эквивалентности.

Алгоритм решения систем уравнений по этому методу:

Преобразовать логическое уравнение, упростить его.

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

Построить таблицу переменных, где задать начальные значения первой переменной (или последней).

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

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

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

Пример1.

¬ X 1 ˅ X 2=1

¬ X 2 ˅ X 3=1

¬ X 3 ˅ X 4=1

¬ X 9 ˅ X 10=1

Начнем с Х1 и посмотрим какие значения эта переменная может принимать: 0 и 1.

Затем рассмотрим каждое из этих значений и посмотрим, какое может быть при этом Х2.

Ответ: 11 решений

Пример 2.

( X 1˄ X 2)˅(¬ X 1˄¬ X 2) ˅( X 1↔ X 3)=1

( X 2˄ X 3)˅(¬ X 2˄¬ X 3) ˅( X 2↔ X 4)=1

(X8˄ X9)˅(¬X8˄¬X9) ˅(X8↔X10)=0

Преобразуем по формуле (A ˄ B )˅ (¬ A ˄ ¬ B )= A ↔ B

Получаем:

( X 1↔ X 2) ˅ ( X 1↔ X 3) =1

( X 2↔ X 3) ˅ ( X 2↔ X 4) =1

( X 8↔ X 9) ˅ ( X 8↔ X 10) =0

Для Х1 =0 - 8 решений

Возьмем Х1=1 и посмотрим какие значение может принимать Х2. Теперь для каждого Х2 рассмотрим какие значения может принимать Х3 и т.д.

Для Х1=1 – 8 решений

Итого 8+8=16 решений

Ответ. 16 решений

Пример 3 .

¬ ( X 1↔ X 2) ˄ ( X 1 ˅ X 3) ˄ (¬ X 1 ˅ ¬ X 3 )=0

¬ ( X 2↔ X 3) ˄ ( X 2 ˅ X 4) ˄ (¬ X 2 ˅ ¬ X 4)=0

….

¬ ( X 8↔ X 9) ˄ ( X 8 ˅ X 10) ˄ (¬ X 8 ˅ ¬ X 10)=0

После преобразований (A ˅ B ) ˄(¬ A ˅¬ B )= ¬( A ↔ B )

получаем:

¬ ( X 1↔ X 2) ˄ ¬ ( X 1↔ X 3)=0

¬ ( X 2↔ X 3) ˄ ¬ ( X 2↔ X 4)=0

…..

¬ ( X 8↔ X 9) ˄ ¬ ( X 8↔ X 10)=0

Возьмем Х1=0 и посмотрим какие значение может принимать Х2. Теперь для каждого Х2 рассмотрим какие значения может принимать Х3 и т.д

Получилось 10 решений для Х1=0

То же самое проделаем для Х1=1. Получим тоже 10 решений

Итого:10+10=20

Ответ: 20 решений.

Пример 4.

(Х1 ˄ Х2) ˅ (¬Х1 ˄ ¬Х2 ) ˅ (Х2 ˄ Х3) ˅ (¬Х2 ˄¬ Х3) =1

(Х2 ˄ Х3) ˅ (¬Х2 ˄ ¬Х3) ˅ (Х3˄ Х4) ˅ (¬Х3 ˄¬ Х4)=1

….

(Х8 ˄ Х9) ˅ (¬Х8˄ ¬Х9) ˅ (Х9 ˄ Х10) ˅ (¬Х9 ˄¬ Х10)=0

Преобразуем по формулам. (A ˄ B )˅ (¬ A ˄ ¬ B )= A ↔ B . Получим:

(Х1↔ Х2) ˅ (Х2↔ Х3)=1

(Х2↔ Х3) ˅ (Х3↔ Х4)=1

(Х3↔ Х4) ˅ (Х4↔ Х5)=1

(Х4↔ Х5) ˅ (Х5↔ Х6)=1

(Х5↔ Х6) ˅ (Х6↔ Х7)=1

(Х6↔ Х7) ˅ (Х7↔ Х8)=1

(Х7↔ Х8) ˅ (Х8↔ Х9)=1

(Х8↔ Х9) ˅ (Х9↔ Х10)=0

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

Пусть Х10=0, тогда Х9=1, Х8=0, Х7=0, Х6=0, а следующие переменные могут принимать разные значения. Будем рассматривать каждое .

Итого 21 решение для Х10=0

Теперь рассмотрим для Х10=1. Получаем тоже 21 решение

Итого:21+21=42

Ответ: 42 решения

Пример 5.

( X 1 ˄ X 2) ˅ (¬ X 1 ˄ ¬ X 2) ˅ (¬ X 3 ˄ X 4) ˅ ( X 3 ˄ ¬ X 4)=1

( X 3 ˄ X 4) ˅ (¬ X 3 ˄ ¬ X 4) ˅ (¬ X 5 ˄ X 6) ˅ ( X 5 ˄ ¬ X 6)=1

( X 5 ˄ X 6) ˅ (¬ X 5 ˄ ¬ X 6) ˅ (¬ X 7 ˄ X 8) ˅ ( X 7 ˄ ¬ X 8)=1

( X 7 ˄ X 8) ˅ (¬ X 7 ˄ ¬ X 8) ˅ (¬ X 9 ˄ X 10) ˅ ( X 9˄ ¬ X 10) =1

Преобразуем по формулам: (¬ A ˄ B ) ˅ ( A ˄ ¬ B )= A ↔ ¬ B

( A ˄ B )˅ (¬ A ˄ ¬ B )= A ↔ B

( X 1↔ X 2) ˅ ( X 3 ↔ ¬ X 4)=1

( X 3↔ X 4) ˅ ( X 5 ↔ ¬ X 6)=1

( X 5↔ X 6) ˅ ( X 7 ↔ ¬ X 8)=1

( X 7↔ X 8) ˅ ( X 9 ↔ ¬ X 10)=1

Рассмотрим какие значения могут принимать Х1 и Х2: (0,0), (0,1), (1,0), (1,1).

Рассмотрим каждый вариант и посмотрим какие значения при этом могут принимать Х3, Х4

Начиная с Х7, Х8 будем сразу записывать количество решений, так как сразу видно, что когда значения одинаковые (1,1) и (0,0), то следующие переменные имеют 4 решения, а когда разные (0,1) и (1,0) – 2 решения.

Итого: 80+80+32=192

Ответ:192 решения

Пример 6.

(Х1↔ Х2) ˅ (Х2 ↔Х3)=1

(Х2↔ Х3) ˅ (Х3↔Х4)=1

(Х3↔ Х4) ˅ (Х4 ↔Х5)=1

….

(Х8↔ Х9) ˅ (Х9 ↔Х10)=1

Возьмем Х1=0 и посмотрим какие значение может принимать Х2. Теперь для каждого Х2 рассмотрим какие значения может принимать Х3 и т.д.

Видим некоторую закономерность: Количество следующих решений равно сумме двух предыдущих.

То же самое для Х1=1 получаем 89 решений

Итого: 89+89=178 решений

Ответ: 178 решений

Решим еще одним способом

(Х1↔ Х2) ˅ (Х2 ↔Х3)=1

(Х2↔ Х3) ˅ (Х3↔Х4)=1

(Х3↔ Х4) ˅ (Х4 ↔Х5)=1

….

(Х8↔ Х9) ˅ (Х9 ↔Х10)=1

Введем замену:

T 1 =(Х1↔ Х2)

T 2 =(Х2↔ Х3)

T 3 =(Х3↔ Х4)

T 4 =(Х4↔ Х5)

T 5 =(Х5↔ Х6)

T 6 =(Х6↔ Х7)

T 7 =(Х7↔ Х8)

T 8 =(Х8↔ Х9)

T 9 =(Х9↔ Х10)

Получаем:

T 1 ˅ T 2=1

T 2 ˅ T 3=1

T 3 ˅ T 4=1

T 4 ˅ T 5=1

T 5 ˅ T 6=1

T 6 ˅ T 7=1

T 7 ˅ T 8=1

T 8 ˅ T 9=1

T 9 ˅ T 10=1

Возьмем T 1=1 и используем свойства дизъюнкции:

НО Вспомним, что

T 1 =(Х1↔ Х2)

T 2 =(Х2↔ Х3) и т.д.

Воспользуемся свойством эквивалентности и убедимся, глядя на таблицу, что

Когда Т =1, то получается два решения. А когда =0 –одно решение.

Следовательно, можно подсчитать количество единиц и умножить их на 2+ количество нулей. Подсчет, так же используя закономерность .

Получается, что количество единиц = предыдущему общему количеству решений Т, а количество нулей равно предыдущему количеству единиц

Итак. Получим. Так как единица дает два решения, то 34*2=68 решений из единицы+21 решение из 0.

Итого 89 решений для Т=1. Аналогичным способом получаем 89 решений для Т=0

Итого 89+89=178

Ответ: 178 решений

Пример 7.

(X 1 ↔ X 2) ˅ (X 3↔ X 4) ˄ ¬(X 1 ↔ X 2) ˅ ¬(X 3↔ X 4)=1

(X 3 ↔ X 4) ˅ (X 5↔ X 6) ˄ ¬(X 3 ↔ X 4) ˅ ¬(X 5↔ X 6)=1

(X 5 ↔ X 6) ˅ (X 7↔ X 8) ˄ ¬(X 5 ↔ X 6) ˅ ¬(X 7↔ X 8)=1

(X 7 ↔ X 8) ˅ (X 9↔ X 10) ˄ ¬(X 7 ↔ X 8) ˅ ¬(X 9↔ X 10)=1

Введем замену:

T 1=(X 1 ↔ X 2)

T 2=(X 3↔ X 4)

T 3=(X 5↔ X 6)

T 4=(X 7 ↔ X 8)

T 5=(X 9↔ X 10)

Получим:

(Т1 ˅ Т2) ˄ ¬(Т1 ˅¬ Т2)=1

(Т2 ˅ Т3) ˄ ¬(Т2˅¬ Т3)=1

(Т3 ˅ Т4) ˄ ¬(Т3 ˅¬ Т4)=1

(Т4 ˅ Т5) ˄ ¬(Т4˅¬ Т5)=1

Рассмотрим какие могут быть Т:

Т1

Т2

Т3

Т4

Т5

Итого

0

1

0

1

0

32

1

0

1

0

1

32

Т K ≠Т К+1 И Т K =Т К+2

Получаем: 2 5 =32 для Т

Итого: 32+32=64

Ответ: 64 решения.

Данной материал содержит презентацию, в которой представлены методы решения логических уравнений и систем логических уравнений в задании В15 (№ 23, 2015) ЕГЭ по информатике. Известно, что это задание является одним из самых сложных среди заданий ЕГЭ. Презентация может быть полезна при проведении уроков по теме "Логика" в профильных классах, а также при подготовке к сдаче ЕГЭ.

Скачать:

Предварительный просмотр:

Чтобы пользоваться предварительным просмотром презентаций создайте себе аккаунт (учетную запись) Google и войдите в него: https://accounts.google.com

Подписи к слайдам:

Решение задания В15 (системы логических уравнений) Вишневская М.П., МАОУ «Гимназия №3» 18 ноября 2013 г., г. Саратов

Задание В15 - одно из самых сложных в ЕГЭ по информатике!!! Проверяются умения: преобразовывать выражения, содержащие логические переменные; описывать на естественном языке множество значений логических переменных, при которых заданный набор логических переменных истинен; подсчитывать число двоичных наборов, удовлетворяющих заданным условиям. Самое сложное, т.к. нет формальных правил, как это сделать, требуется догадка.

Без чего не обойтись!

Без чего не обойтись!

Условные обозначения конъюнкция: A /\ B , A  B , AB , А &B, A and B дизъюнкция: A \ / B , A + B , A | B , А or B отрицание:  A , А, not A эквиваленция: A  В, A  B, A  B исключающее «или»: A  B , A xor B

Метод замены переменных Сколько существует различных наборов значений логических переменных х1, х2, …, х9, х10, которые удовлетворяют всем перечисленным ниже условиям: ((x1 ≡ x2) \/ (x3 ≡ x4)) /\ (¬(x1 ≡ x2) \/ ¬(x3 ≡ x4)) = 1 ((x3 ≡ x4) \/ (x5 ≡ x6)) /\ (¬(x3 ≡ x4) \/ ¬(x5 ≡ x6)) = 1 ((x5 ≡ x6) \/ (x7 ≡ x8)) /\ (¬(x5 ≡ x7) \/ ¬(x7 ≡ x8)) = 1 ((x7 ≡ x8) \/ (x9 ≡ x10)) /\ (¬(x7 ≡ x8) \/ ¬(x9 ≡ x10)) = 1 В ответе не нужно перечислять все различные наборы х1, х2, …, х9, х10, при которых выполняется данная система равенств. В качестве ответа необходимо указать количество таких наборов (демо-версия 2012 г.)

Решение Шаг 1. Упрощаем, выполнив замену переменных t1 = x1  x2 t2 = x3  x4 t3 = x5  x6 t4 = x7  x8 t5 = x9  x10 После упрощения: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) =1 (t2 \/ t3) /\ (¬t2 \/ ¬ t3) =1 (t3 \/ t4) /\ (¬t3 \/ ¬ t4) =1 (t4 \/ t5) /\ (¬t4 \/ ¬ t5) =1 Рассмотрим одно из уравнений: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) =1 Очевидно, оно =1 только если одна из переменных равна 0, а другая – 1. Воспользуемся формулой для выражения операции XOR через конъюнкцию и дизъюнкцию: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) = t1  t2 = ¬(t1 ≡ t2) =1 ¬(t1 ≡ t2) =1 ¬(t2 ≡ t3) =1 ¬(t3 ≡ t4) =1 ¬(t4 ≡ t5) =1

Шаг2. Анализ системы ¬(t1 ≡ t2) =1 ¬(t2 ≡ t3) =1 ¬(t3 ≡ t4) =1 ¬(t4 ≡ t5) =1 t1 t2 t3 t4 t5 0 1 0 1 0 1 0 1 0 1 Т.к. tk = x2k-1 ≡ x2k (t1 = x1  x2 ,….), то каждому значению tk соответствует две пары значений x2k-1 и x2k , например: tk =0 соответствуют две пары - (0,1) и (1,0) , а tk =1 – пары (0,0) и (1,1).

Шаг3. Подсчет числа решений. Каждое t имеет 2 решения, количество t – 5. Т.о. для переменных t существует 2 5 = 32 решения. Но каждому t соответствует пара решений х, т.е. исходная система имеет 2*32 = 64 решения. Ответ: 64

Метод исключения части решений Сколько существует различных наборов значений логических переменных х1, х2, …, х5, y1,y2,… , y5 , которые удовлетворяют всем перечисленным ниже условиям: (x1→ x2)∧(x2→ x3)∧(x3→ x4)∧(x4→ x5) =1; (y1→ y2)∧(y2→ y3)∧(y3→ y4) ∧(y4→ y5) =1; y5→ x5 =1. В ответе не нужно перечислять все различные наборы х1, х2, …, х5, y 1 ,y2,… , y5, при которых выполняется данная система равенств. В качестве ответа необходимо указать количество таких наборов.

Решение. Шаг1. Последовательное решение уравнений х1 1 0 х2 1 0 1 х3 1 0 1 1 х4 1 0 1 1 1 х5 1 0 1 1 1 1 Первое уравнение – конъюнкция нескольких операций импликации, равна 1, т.е. каждая из импликаций истинна. Импликация ложна только в одном случае, когда 1  0, во всех других случаях (0  0, 0  1, 1  1) операция возвращает 1. Запишем это в виде таблицы:

Шаг1. Последовательное решение уравнений Т.о. получено 6 наборов решений для х1,х2,х3,х4,х5: (00000), (00001), (00011), (00111), (01111), (11111). Рассуждая аналогично, приходим к выводу, что для y1, y2, y3, y4, y5 существует такой же набор решений. Т.к. уравнения эти независимы, т.е. в них нет общих переменных, то решением этой системы уравнений (без учета третьего уравнения) будет 6*6= 36 пар «иксов» и «игреков». Рассмотрим третье уравнение: y5→ x5 =1 Решением являются пары: 0 0 0 1 1 1 Не является решением пара: 1 0

Сопоставим полученные решения Там, где y5 =1, не подходят x5=0. таких пар 5. Количество решений системы: 36-5= 31 . Ответ: 31 Понадобилась комбинаторика!!!

Метод динамического программирования Сколько различных решений имеет логическое уравнение x 1 → x 2 → x 3 → x 4 → x 5 → x 6 = 1, где x 1, x 2, …, x 6 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количеств о таких наборов.

Решение Шаг1. Анализ условия Слева в уравнении последовательно записаны операции импликации, приоритет одинаков. Перепишем: ((((X 1 → X 2) → X 3) → X 4) → X 5) → X 6 = 1 NB! Каждая следующая переменная зависит не от предыдущей, а от результата предыдущей импликации!

Шаг2. Выявление закономерности Рассмотрим первую импликацию, X 1 → X 2. Таблица истинности: X 1 X 2 X 1 → X 2 0 0 1 0 1 1 1 0 0 1 1 1 Из одного 0 получили 2 единицы, а из 1 получили один 0 и одну 1. Всего один 0 и три 1, это результат первой операции.

Шаг2. Выявление закономерности Подключив к результату первой операции x 3 , получим: F(x 1 ,x 2) x 3 F(x 1 ,x 2)  x 3 0 0 1 0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 Из двух 0 – две 1, из каждой 1 (их 3) по одному 0 и 1 (3+3)

Шаг 3. Вывод формулы Т.о. можно составить формулы для вычисления количества нулей N i и количества единиц E i для уравнения с i переменными: ,

Шаг 4. Заполнение таблицы Заполним слева направо таблицу для i = 6, вычисляя число нулей и единиц по приведенным выше формулам; в таблице показано, как строится следующий столбец по предыдущему: : число переменных 1 2 3 4 5 6 Число нулей N i 1 1 3 5 11 21 Число единиц E i 1 2*1+1= 3 2*1+3= 5 11 21 43 Ответ: 43

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

Решение Заметим, что J → K = ¬ J  K Введем замену переменных: J → K=А, M  N  L =В Перепишем уравнение с учетом замены: (A → B)  (B → A)  (M → J)=1 4. (A  B)  (M → J)= 1 5. Очевидно, что A  B при одинаковых значениях А и В 6. Рассмотрим последнюю импликацию M → J =1 Это возможно, если: M=J=0 M=0, J=1 M=J=1

Решение Т.к. A  B , то При M=J=0 получаем 1 + К=0. Нет решений. При M=0, J=1 получаем 0 + К=0, К=0, а N и L - любые, 4 решения: ¬ J  K = M  N  L K N L 0 0 0 0 0 1 0 1 0 0 1 1

Решение 10. При M=J=1 получаем 0+К=1 *N * L , или K=N*L, 4 решения: 11. Итого имеет 4+4=8 решений Ответ: 8 K N L 0 0 0 0 0 1 0 1 0 1 1 1

Источники информации: О.Б. Богомолова, Д.Ю. Усенков. В15: новые задачи и новое решение // Информатика, № 6, 2012, с. 35 – 39. К.Ю. Поляков. Логические уравнения // Информатика, № 14, 2011, с. 30-35. http://ege-go.ru/zadania/grb/b15/ , [ Электронный ресурс ] . http://kpolyakov.narod.ru/school/ege.htm , [ Электронный ресурс ] .

Размер: px

Начинать показ со страницы:

Транскрипт

1 Решение логических уравнений и систем логических уравнений Пусть F(x, x2, xn) логическая функция от n переменных. Логическое уравнение имеет вид: F(x, x2, xn) = С, где константа С имеет значение или. Логическое уравнение может иметь от до 2 n различных решений. Если С равно, то решениями являются все те наборы переменных из таблицы истинности, на которых функция F принимает значение истина (). Оставшиеся наборы являются решениями уравнения при C, равном нулю. Можно всегда рассматривать только уравнения вида: F(x, x2, xn) = Действительно, пусть задано уравнение: F(x, x2, xn) = В этом случае можно перейти к эквивалентному уравнению: F(x, x2, xn) = Рассмотрим систему из k логических уравнений: F(x, x2, xn) = F2(x, x2, xn) = { Fk(x, x2, xn) = Решением системы является набор переменных, на котором выполняются все уравнения системы. В терминах логических функций для получения решения системы логических уравнений следует найти набор, на котором истинна логическая функция Ф, представляющая конъюнкцию исходных функций F: Ф = F F2 Fk Если число переменных невелико, например, менее 5, то нетрудно построить таблицу истинности для функции Ф, что позволяет сказать, сколько решений имеет система и каковы наборы, дающие решения. В некоторых задачах ЕГЭ по нахождению решений системы логических уравнений число переменных доходит до значения. Тогда построить таблицу истинности становится практически неразрешимой задачей. Для решения задачи требуется другой подход. Для произвольной системы уравнений не существует общего способа, отличного от перебора, позволяющего решать такие задачи. В предлагаемых на экзамене задачах решение обычно основано на учете специфики системы уравнений. Однако, повторю, что кроме перебора всех вариантов набора переменных, общего способа решения задачи нет. Решение нужно строить исходя из представленной системы. Часто полезно провести предварительное упрощение системы уравнений, используя известные законы логики. Другой полезный прием решения этой задачи состоит в следующем. Нам интересны не все наборы, а только те, на которых функция Ф имеет значение. Вместо построения полной таблицы истинности будем строить ее аналог - бинарное дерево решений. Каждая ветвь этого дерева соответствует

2 одному решению и задает набор, на котором функция Ф имеет значение. Число ветвей в дереве решений совпадает с числом решений системы уравнений. Что такое бинарное дерево решений и как оно строится, поясню на примерах нескольких задач. Задача Сколько существует различных наборов значений логических переменных x, x2, x3, x4, x5, y, y2, y3, y4, y5, которые удовлетворяют системе из двух уравнений? (x x2) /\ (x2 x3) /\ (x3 x4) /\ (x4 x5) = { (y y2) /\ (y2 y3) /\ (y3 y4) /\ (y4 y5) = Ответ: Система имеет 36 различных решений. Система уравнений включает два уравнения. Найдем число решений для первого уравнения, зависящего от 5 переменных x, x2, x5. Первое уравнение можно в свою очередь рассматривать как систему из 5 уравнений. Как было показано, система уравнений фактически представляет конъюнкцию логических функций. Справедливо и обратное утверждение, - конъюнкцию условий можно рассматривать как систему уравнений. Построим дерево решений для импликации (x x2) - первого члена конъюнкции, который можно рассматривать как первое уравнение. Вот как выглядит графическое изображение этого дерева: X X2 Дерево состоит из двух уровней по числу переменных уравнения. Первый уровень описывает первую переменную X. Две ветви этого уровня отражают возможные значения этой переменной и. На втором уровне ветви дерева отражают только те возможные значения переменной X2, для которых уравнение принимает значение истина. Поскольку уравнение задает импликацию, то ветвь, на которой X имеет значение, требует, чтобы на этой ветви X2 имело значение. Ветвь, на которой X имеет значение, порождает две ветви со значениями X2, равными и. Построенное дерево задает три решения, на которых импликация X X2 принимает значение. На каждой ветви выписан соответствующий набор значений переменных, дающий решение уравнения. Вот эти наборы: {(,), (,), (,)} Продолжим построение дерева решений, добавляя следующее уравнение, следующую импликацию X2 X3. Специфика нашей системы уравнений в том, что каждое новое уравнение системы использует одну переменную из предыдущего уравнения, добавляя одну новую переменную. Поскольку переменная X2 уже имеет значения на дереве, то на всех ветвях, где переменная X2 имеет значение, переменная X3 также будет иметь значение. Для таких ветвей построение дерева продолжается на следующий уровень, но новые ветви не появляются. Единственная ветвь, где переменная X2 имеет значение, даст разветвление на две ветви, где переменная X3 получит значения и. Таким образом, каждое добавление нового уравнения, учитывая его специфику, добавляет одно решение.

3 Исходное первое уравнение: (x x2) /\ (x2 x3) /\ (x3 x4) /\ (x4 x5) = имеет 6 решений. Вот как выглядит полное дерево решений для этого уравнения: X X2 X3 X4 X5 Второе уравнение нашей системы аналогично первому: (y y2) /\ (y2 y3) /\ (y3 y4) /\ (y4 y5) = Разница лишь в том, что в уравнении используются переменные Y. Это уравнение также имеет 6 решений. Поскольку каждое решение для переменных Xi может быть скомбинировано с каждым решением для переменных Yj, то общее число решений равно 36. Заметьте, построенное дерево решений дает не только число решений (по числу ветвей), но и сами решения, выписанные на каждой ветви дерева. Задача 2 Сколько существует различных наборов значений логических переменных x, x2, x3, x4, x5, y, y2, y3, y4, y5, которые удовлетворяют всем перечисленным ниже условиям? (x x2) ^ (x2 x3) ^ (x3 x4) ^ (x4 x5) = {(y y2) ^ (y2 y3) ^ (y3 y4) ^ (y4 y5) = (x y) = Ответ: 3 Эта задача является модификацией предыдущей задачи. Разница в том, что добавляется еще одно уравнение, связывающее переменные X и Y. Из уравнения X Y следует, что когда X имеет значение (одно такое решение существует), то и Y имеет значение. Таким образом, существует один набор, на котором

4 X и Y имеют значения. При X, равном, Y может иметь любое значение, как, так и. Поэтому каждому набору с X, равном, а таких наборов 5, соответствует все 6 наборов с переменными Y. Следовательно, общее число решений равно 3. Задача 3 Сколько решений имеет уравнение: (X X2) (X2 X3) (X3 X4) (X4 X5) (X5 X) = Ответ: 2 Вспоминания основные эквивалентности, запишем наше уравнение в виде: (X X2) (X2 X3) (X3 X4) (X4 X5) (X5 X) = Циклическая цепочка импликаций означает тождественность переменных, так что наше уравнение эквивалентно уравнению: X X2 X3 X4 X5 = Это уравнение имеет два решения, когда все Xi равны либо, либо. Задача 4 Сколько решений имеет уравнение: (X X2) (X2 X3) (X3 X4) (X4 X2) (X4 X5) = Ответ: 4 Так же, как и в задаче 2, от циклических импликаций перейдем к тождествам, переписав уравнение в виде: (X X2) (X2 X3 X4) (X4 X5) = Построим дерево решений для этого уравнения: X X2 X3 X4 X5

5 Задача 4 Сколько решений имеет следующая система уравнений? Ответ: 64 ((X X2) (X3 X4)) ((X X2) (X3 X4)) = ((X3 X4) (X5 X6)) ((X3 X4) (X5 X6)) = ((X5 X6) (X7 X8)) ((X5 X6) (X7 X8)) = {((X7 X8) (X9 X)) ((X7 X8) (X9 X)) = Перейдем от переменных к 5 переменным, введя следующую замену переменных: Y = (X X2); Y2 = (X3 X4); Y3 = (X5 X6); Y4 = (X7 X8); Y5 = (X9 X); Тогда первое уравнение примет вид: (Y Y2) (Y Y2) = Уравнение можно упростить, записав его в виде: (Y Y2) = Переходя к традиционной форме, запишем систему после упрощений в виде: (Y Y2) = (Y2 Y3) = { (Y3 Y4) = (Y4 Y5) = Дерево решений для этой системы простое и состоит из двух ветвей с чередующимися значениями переменных: Y Y2 Y3 Y4 Y5 Возвращаясь к исходным переменным X, заметим, что каждому значению переменной Y соответствует 2 значения переменных X, поэтому каждое решение в переменных Yпорождает 2 5 решений в переменных X. Две ветви порождают 2 * 2 5 решений, так что общее число решений равно 64. Как видите, каждая задача на решение системы уравнений требует своего подхода. Общим приемом является выполнение эквивалентных преобразований для упрощения уравнений.

6 Общим приемом является и построение деревьев решений. Применяемый подход частично напоминает построение таблицы истинности с той особенностью, что строятся не все наборы возможных значений переменных, а лишь те, на которых функция принимает значение (истина). Часто в предлагаемых задачах нет необходимости в построении полного дерева решений, поскольку уже на начальном этапе удается установить закономерность появления новых ветвей на каждом следующем уровне, как это сделано, например, в задаче.

Путилов Виктор Васильевич МАОУ СОШ 46 Системы логических уравнений. Оглавление Замечание о замене переменных.... Задачи содержащие импликацию или ее эквивалентную запись....2 Наличие дополнительного условия...6

Решение системы логических уравнений. Сколько решений имеет уравнение A BB C C D = 0 Количество наборов переменных равно =. Можно составить таблицу истинности и проверить, сколько наборов соответствуют

Построение и анализ таблиц истинности логических выражений. ЕГЭ 2015 2 (базовый уровень, время 3 мин) Пример Р-13. Каждое логическое выражение A и B зависит от одного и того же набора из 5 переменных.

Н Б Рогов Как научиться решать задание B15 ЕГЭ по информатике (системы логических уравнений) за 180+ минут Материалы для занятий Раздел в сети: http://basicschoolru/?page=eam_info_b15 Теоретическое введение:

B4 Тема: Преобразование логических выражений. Про обозначения К сожалению, обозначения логических операций И, ИЛИ и НЕ, принятые в «серьезной» математической логике (,), неудобны, интуитивно непонятны

Математика и математическое моделирование УДК 004.023 Семенов Сергей Максимович Владивостокский государственный университет экономики и сервиса Россия. Владивосток Об одном способе решения систем логических

B4 (высокий уровень, время 1 мин) Тема: Преобразование логических выражений. Про обозначения К сожалению, обозначения логических операций И, ИЛИ и НЕ, принятые в «серьезной» математической логике (,),

B0 (высокий уровень, время 0 мин) Тема: Преобразование логических выражений. Про обозначения К сожалению, обозначения логических операций И, ИЛИ и НЕ, принятые в «серьезной» математической логике (,),

19022017 Битовые операции в задачах КИМ ЕГЭ по информатике Часть II КЮ Поляков, дтн, учитель информатики ГБОУ СОШ 163, г Санкт-Петербург В данной статье рассматриваются задачи следующего типа впервые эти

Самостоятельная работа по теме «Способы задания логических функций» 1. Вычислить значение функции F(x, y, z) = на наборе переменных (1, 1, 0). 3. Определить эквивалентность функций F(x, y, z) = и G(x,

Логика это наука, изучающая методы установления истинности или ложности одних высказываний на основе истинности или ложности других высказываний. Высказывание (суждение) некоторое предложение, которое

B высокий уровень, время 0 мин) К. Поляков, 009-0 Тема: Преобразование логических выражений. Про обозначения К сожалению, обозначения логических операций И, ИЛИ и НЕ, принятые в «серьезной» математической

Задача 1: Дан фрагмент таблицы истинности выражения F: Каким выражением может быть F? X Y Z F 0 0 0 0 0 0 1 0 1 1 1 1 1) X /\ Y /\ Z 2) X \/ Y \/ Z 3) X \/ Y \/ Z 4) X /\ Y /\ Z Рассмотрим первое выражение

ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ (продолжение) Число булевых функций от n переменных находится по формуле: P2 (n) = 2 2n Логических функций двух переменных 6 Наиболее часто употребляются следующие функции: f (x,

Решения задач по двузначной логике Ф.Г. Кораблев Задача 1. Для функции f(x, y, z) = ((x y) (x z)) (z x) найти существенные и фиктивные переменные, произвести операцию исключения фиктивных переменных. Решение.

051216 Битовые операции в задачах КИМ ЕГЭ по информатике Часть II КЮ Поляков, дтн, учитель информатики ГБОУ СОШ 163, г Санкт-Петербург В данной статье рассматриваются задачи следующего типа впервые эти

Мирончик Е.А., учитель информатики, г. Новокузнецк Решение задания ЕГЭ-18 с битовыми операциями Описанный метод демонстрирует способ решения на основе тождественных переходов, т.е. знак равно «работает»

Тема: Основные понятия математической логики. Примерные вопросы Про обозначения К сожалению, обозначения логических операций И, ИЛИ и НЕ, принятые в «серьезной» математической логике (,), неудобны, интуитивно

Часть 1 1. Укажите, какое логическое выражение равносильно выражению A /\ (B \/ C). 1) A \/ B \/ C 2) A /\ B /\ C 3) A /\ B /\ C 4) A /\ B /\ C Решение: Применяя формулу де Моргана (B \/ C) = B /\ C и

Глинка Н.В. Используемые обозначения Отрицание Умножение (конъюнкция) Сложение (дизъюнкция) Импликация Эквивалентность Примеры задач до 2010 учебного года Сколько различных решений имеет уравнение ((K

Битовые операции в задачах КИМ по информатике Типы задач В данном вебинаре рассматриваются задачи следующего типа (впервые эти задачи появились в КИМ на ЕГЭ 2015 года): Введжм выражение M & K, обозначающее

Практическая работа 6 Решение логических задач с применением законов алгебры логики Цель работы: закрепление умений преобразовывать логические выражения с использованием законов алгебры логики, вычислять

A10 (базовый уровень, время 1 мин) Тема: Преобразование логических выражений. Формулы де Моргана. Про обозначения К сожалению, обозначения логических операций И, ИЛИ и НЕ, принятые в «серьезной» математической

Гурская К.А., Ивин В.В., Семёнов С.М. Решение задач математической логики в ЕГЭ по информатике 1 УДК 004.9 Гурская К.А., Ивин В.В., Семёнов С.М. Учебное пособие «Решение задач математической логики в ЕГЭ

ОГЛАВЛЕНИЕ Предисловие............................. 3 Глава 1. Математическая логика................. 4 1. Алгебра высказываний.................. 4 2. Булевы алгебры...................... 12 3. Исчисление

ЛЕКЦИЯ 5 ЛОГИЧЕСКИЕ ОПЕРАЦИИ В ИНФОРМАТИКЕ 1. Математическая логика и информатика 2. Логические выражения и логические операции 3. Построение таблиц истинности и логических функций 4. Законы логики и правила

B5 высокий уровень, время 0 мин) Тема: Преобразование логических выражений. Про обозначения К сожалению, обозначения логических операций И, ИЛИ и НЕ, принятые в «серьезной» математической логике,), неудобны,

Алгебра логики Алгебра логики формальная логическая теория, раздел математической логики, разработанный в XIX веке английским математиком Джорджем Булем. В алгебре логики используются алгебраические методы

2 (базовый уровень, время мин) Тема: Построение и анализ таблиц истинности логических выражений. Про обозначения К сожалению, обозначения логических операций И, ИЛИ и НЕ, принятые в «серьезной» математической

A8 (базовый уровень, время 1 мин) Тема: Преобразование логических выражений. Формулы де Моргана. Про обозначения К сожалению, обозначения логических операций И, ИЛИ и НЕ, принятые в «серьезной» математической

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

Основы логики. Логические операции и таблицы истинности Основы логики. Логические операции и таблицы истинности На данной странице будут рассмотрены 6 логических операций: конъюнкция, дизъюнкция, инверсия,

Тождества Булевой алгебры Основная задача математической логики на основании ложности или истинности простых высказываний определить значение сложного высказывания. Логические операции алгебре высказываний

Муниципальное бюджетное общеобразовательное учреждение города Абакана «Средняя общеобразовательная школа 11» Методическая разработка по теме Решение заданий типа 18 ЕГЭ по информатике Атюшкина Марина Валерьевна,

Тема 4. Логические основы ЭВМ 1.ОСНОВНЫЕ СВЕДЕНИЯ ИЗ АЛГЕБРЫ ЛОГИКИ... 1 2. ЗАКОНЫ АЛГЕБРЫ ЛОГИКИ... 4 3. ПОНЯТИЕ О МИНИМИЗАЦИИ ЛОГИЧЕСКИХ ФУНКЦИЙ... 6 4.ТЕХНИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ ЛОГИЧЕСКИХ ФУНКЦИЙ...

Тема 9. Логические основы ЭВМ. 1. Логика. Информация, обрабатываемая в ЭВМ, представляется с помощью физических величин, которые могут принимать только два устойчивых состояния и называются «двоичные переменные».

Иррациональные неравенства Неравенства, в которых переменная содержится под знаком корня, называются иррациональными Основным методом решения иррациональных неравенств является метод сведения исходного

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

Краевой конкурс учебно-исследовательских и проектных работ учащихся «Прикладные вопросы математики» Алгебра Алгебра логики Семушева Алена Сергеевна, МОУ «Лицей» г. Перми, кл. Боркова Ольга Владимировн,

К. Поляков, 009-0 B5 высокий уровень, время 0 мин) Тема: Преобразование логических выражений. Про обозначения К сожалению, обозначения логических операций И, ИЛИ и НЕ, принятые в «серьезной» математической

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ 1 Линейные уравнения первого порядка, уравнение Бернулли Уравнение в полных дифференциалах Линейным дифференциальным уравнением первого порядка называется уравнение + p(= q(Если

ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ Московский государственный технический университет имени Н.Э. Баумана Факультет «Фундаментальные науки» Кафедра «Математическое моделирование» À.Í. Êàíàòíèêîâ ÄÈÑÊÐÅÒÍÀß ÌÀÒÅÌÀÒÈÊÀ

A9 (базовый уровень, время 2 мин) Тема: Построение таблиц истинности логических выражений. Про обозначения К сожалению, обозначения логических операций И, ИЛИ и НЕ, принятые в «серьезной» математической

Мирончик Е.А., МБ НОУ «Лицей», г. Новокузнецк Метод отображения Задание. Сколько решений имеет система: Все уравнения, включенные в систему, однотипны, и в каждое уравнение включено три переменных. Зная

Федеральное агентство по образованию Уральский государственный экономический университет Ю. Б. Мельников Булевы и логические функции Раздел электронного учебника для сопровождения лекции e-mail: [email protected],

Е.В.Просолупов 42. Булева алгебра. Функции алгебры логики 1 Булевы функции Будем рассматривать булевы функции функции, аргументы и значения которых принимают значения истина и ложь. Истину и ложь будем

Федеральное агентство по образованию Уральский государственный экономический университет Ю. Б. Мельников Булевы и логические функции Раздел электронного учебника для сопровождения лекции Изд. 3-е, испр.

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ Федеральное государственное автономное образовательное учреждение высшего профессионального образования «НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ ТОМСКИЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

Практическая работа 1 Логические операции. Равносильность формул Цель работы: Научиться строить таблицы истинности логических высказываний и преобразовывать формулы, используя основные равносильности Содержание

Говорят, что когда Аристотель придумал логику, он на радостях устроил пир и велел заколоть 40 баранов. С тех пор бараны логику не любят. Основные понятия алгебры логики 10 класс, 2017-2018 учебный год

Дифференциальные уравнения первого порядка разрешенные относительно производной Теорема существования и единственности решения В общем случае дифференциальное уравнение первого порядка имеет вид F ()

Лекция 2. Конъюнктивные нормальные формы. Имплицента, простая имплицента функции. Сокращенная КНФ функции алгебры логики. Способы построения сокращенной КНФ. Лектор Селезнева Светлана Николаевна [email protected]

ЛОГИКА ВЫСКАЗЫВАНИЙ Высказывания Высказывание повествовательное предложение, содержание которого можно оценить либо как истинное, либо как ложное. Различают: абсолютно истинные высказывания, абсолютно

Доля П.Г. Харьковский Национальный Университет механико математический факультет Дискретная математика. Конспект лекций. Оглавление 1. Алгебра высказываний и логика. 1.1 Высказывания и логические операции...

Законы алгебры логики Это интересно! Математика и закон де Моргана Как вы запишите математически принадлежность точки x отрезку ? Это можно сделать так: 2 x 5. Это означает, что одновременно должны

Математическая логика и теория алгоритмов Первухин Михаил Александрович Логическое следствие в АВ Говорят, что формула ψ x 1, x n АВ является логическим следствием формул φ 1 (x 1, x n), φ m x 1,

ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ Московский государственный технический университет имени Н.Э. Баумана Факультет «Фундаментальные науки» Кафедра «Математическое моделирование» À.Í. Êàíàòíèêîâ

ЛЕКЦИЯ 21 СКОБКИ ПУАССОНА. ТЕОРЕМА ЯКОБИ-ПУАССОНА. КАНОНИЧЕСКИЕ ПРЕОБРАЗОВАНИЯ 1. Скобки Пуассона На прошлой лекции вводилось понятие скобки Лагранжа. Это выражение было составлено из частных производных

8 задание ЕГЭ («Знание основных понятий и законов математической логики») ЗАКОНЫ АЛГЕБРЫ ЛОГИКИ Х = Х X /\ Y = Y /\ X X \/ Y = Y \/ X (X /\ Z) \/ (Y /\ Z)=(X \/ Y) /\ Z A\/ = A A/\ = A A/\ =. ЗАКОНЫ АЛГЕБРЫ

ГЛАВА 6 Формализм скобок Пуассона в классической механике 61 Скобки Пуассона Скобки Пуассона Пусть даны две динамические величины две функции канонических переменных и времени t: (и (Скобкой Пуассона

Лабораторная работа АЛГОРИТМ БЕРЛЕКЭМПА-МЕССИ ДЛЯ НАХОЖДЕНИЯ КОЭФФИЦИЕНТОВ ОБРАТНОЙ СВЯЗИ ГЕНЕРАТОРА ПСЕВДОСЛУЧАЙНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ Рассмотрим как можно восстановить полином задающий обратные связи

К.Ю. Поляков, М.А. Ройтберг Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, 0 http://kpolkov.sp.ru К.Ю. Поляков, М.А. Ройтберг, 0 http://kpolkov.sp.ru Постановка

Битовые операции в задачах КИМ ЕГЭ по информатике К.Ю. Поляков, д.т.н., учитель информатики ГБОУ СОШ 163, г. Санкт-Петербург В данной статье рассматриваются задачи следующего типа (впервые эти задачи появились

Министерство образования Российской федерации Донской государственный технический университет Кафедра «Высшая математика» Задачи по дискретной математике Ростов-на-Дону 2001 УДК 517 Составители: Баранов

Ребята, мы продолжаем изучать большую тему логарифмов, сегодня мы с вами посмотрим, как решать различные уравнения, в которых есть логарифмы. Логарифмическим уравнением, называется уравнение вот такого

A3 (базовый уровень, время 2 мин) Тема: Построение таблиц истинности логических выражений. Про обозначения К сожалению, обозначения логических операций И, ИЛИ и НЕ, принятые в «серьезной» математической

Время выполнения 4 часа. ЛАБОРАТОРНАЯ РАБОТА 2 АЛГЕБРА ЛОГИКИ Цель работы Изучить основы алгебры логики. Задачи лабораторной работы В результате прохождения занятия студент должен: 1) знать: определения

Неравенства С С Подготовка к ЕГЭ 0 (материал для лекции для учителей 8040) Прокофьев АА aaprokof@yanderu Основные способы решения: Задачи С Решение неравенства на промежутках Упрощение неравенства и сведение

Приложение 1 ГРУППЫ, КОЛЬЦА, ПОЛЯ Для криптографии алгебра является одним из основных инструментов в теоретических исследованиях и практических построениях криптографических преобразований Поэтому в этом