Системы уравнений
<<  Системы логических уравнений в задачах ЕГЭ по информатике Системы уравнений с двумя переменными  >>
Решение систем логических уравнений
Решение систем логических уравнений
В15
В15
В15
В15
В15
В15
В15
В15
В15
В15
В15
В15
В15
В15
Декабрь 2013
Декабрь 2013
Решение: Не должно быть чередований – 10 Рассмотрим возможные варианты
Решение: Не должно быть чередований – 10 Рассмотрим возможные варианты
В15
В15
В15
В15
В15
В15
Рассмотрим все значения Х отдельно: (У1
Рассмотрим все значения Х отдельно: (У1
Сколько существует различных наборов значений логических переменных
Сколько существует различных наборов значений логических переменных
((Х1? х2)
((Х1? х2)
Сколько существует различных наборов значений логических переменных
Сколько существует различных наборов значений логических переменных
Получаем еще 5 наборов значений, которые удовлетворяют преобразованной
Получаем еще 5 наборов значений, которые удовлетворяют преобразованной
Сколько существует различных наборов значений логических переменных
Сколько существует различных наборов значений логических переменных
(Х2? Х1)
(Х2? Х1)
В15
В15

Презентация на тему: «Решение систем логических уравнений». Автор: Любовь Николаевна. Файл: «Решение систем логических уравнений.pptx». Размер zip-архива: 2647 КБ.

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

содержание презентации «Решение систем логических уравнений.pptx»
СлайдТекст
1 Решение систем логических уравнений

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

В15

2 В15

В15

Сколько различных решений имеет система логических уравнений (x1 ? x2) ? (x3 ? x4) = 1 (x3 ? x4) ? (x5 ? x6) = 1 где x1, x2, …, x6 – логические переменные? Метод замены переменных. Y1 = x1 ? x2, Y2 = x3 ? x4, Y3 = x5 ? x6 Каждая из новых переменных независима от других, это важно! Система запишется в виде: Y1 ? Y2 = 1 Y2 ? Y3 = 1 Можно объединить эти уравнения в одно (Y1 ? Y2) ? (Y2 ? Y3) = 1 Чтобы это равенство было выполнено, ни одна из импликаций не должна быть ложной, то есть в битовой цепочке переменных Y1, Y2, Y3 не должно быть последовательности «10». Вернемся к исходным переменным; импликация x1 ? x2 =0 при наборе (x1,x2) = (1,0) и x1 ? x2 =1 (один набор) при трёх наборах (x1,x2) = {(0,0), (0,1), (1,1)} – три набора. Учитывая, что Y1, Y2, Y3 независимы, для каждой строки таблицы перемножим количество вариантов комбинация исходных переменных: Сложим все результаты: 1 + 3 + 9 + 27 = 40. Ответ: 40.

3 В15

В15

Сколько различных решений имеет логическое уравнение X1 ? X2 ? X3 ? X4 ? X5 ? X6 = 1 Метод динамического программирования: Порядок выполнения операций определяется приоритетом этих операций. Операции, имеющие одинаковый приоритет, выполняются слева направо: ((((X1 ? X2) ? X3) ? X4) ? X5) ? X6 каждая логическая переменная может принимать значение «истина» (1) или «ложь» (0); для набора из 6 независимых логических переменных существует 26 =64 разных комбинаций значений этих переменных; импликация X1 ? X2 дает в трёх случаях 1, и в одном – 0 : Проанализируем как меняется количество решений, если «подключить» следующую переменную: если X1=0, то X1 ? X2 =1 (из К нулей получаются 2К единиц) если X1=1, то X1 ? X2 =0 при X2 =0 и X1 ? X2 =1 при X2 =1 (из К единиц получаются К нулей и К единиц); составим формулы для вычисления количества нулей и количества единиц Еi для уравнения с i переменными: для одной переменной имеем 1 ноль и 1 единицу, поэтому начальные условия для расчёта: составим таблицу:

4 В15

В15

ВАРИАНТ 2. X1 ? X2 ? X3 ? X4 ? X5 ? X6 = 1 для набора из 6 независимых логических переменных существует 26 =64 разных комбинаций значений этих переменных; если X6 =1, то левая часть уравнения равна 1, то есть равенство выполняется; при X6 =0 и (X1 ? X2 ? X3 ? X4 ? X5)=1 получим 1 ? X6 = 1 ?0 = 0 – не подходит; к-во решений 26-1 = 32; 2. проверим отдельно случаи X5 =0 и X5 =1: X6 = 0 и X5 =1; условие (X1 ? X2 ? X3 ? X4 ? X5)=0 не выполняется, решений нет; X6 = X5 =0, (X1 ? X2 ? X3 ? X4 ? X5)=0 выполняется только при (X1 ? X2 ? X3 ? X4)=1; если X4 =1, это условие всегда верно, поэтому получаем еще 8 решений – 8 комбинаций, где X6 = X5 =0 и X4 =1; 3. случай X6 = X5 = X4 =0; условие (X1 ? X2 ? X3 ? 0)=1 верно при (X1 ? X2 ? X3)=0, это сразу дает X3 =0 и (X1 ? X2)=1 при (X6 = X5 = X4 = X3 =0) условие (X1 ? X2)=1 истинно в трёх случаях: (X1,X2) =(0,0) , (0,1) и (1,1) - ещё 3 решения. Ответ: 32 + 8 + 3 = 43 решения.

5 В15

В15

(x1 ? x2) ? (x2 ? 3) ? (x3 ? x4) ? (x4 ? x5 ) = 1 (Y1 ? Y2) ? (Y2 ? Y3) ? (Y3 ? Y4) ? (Y4 ? Y5 ) = 1 x1 ? Y1 =1 Составим таблицы для каждого уравнения: (x1 ? x2) ? (x2 ? 3) ? (x3 ? x4) ? (x4 ? x5 ) = 1

Ответ: 6*6 – 5 = 31

Уравнение имеет 6 решений

(Y1 ? Y2) ? (Y2 ? Y3) ? (Y3 ? Y4) ? (Y4 ? Y5 ) = 1

Уравнение имеет 6 решений

1-у и 2-улог.Уравнения имеют 6х6=36 решений .

x1?y1 =1 исключим из общего решения значения, где х1?у1=0 (1?0), т.е. исключаются 1-ые значения х1=1 и значение у1=1. Таких значений 5.

6 В15

В15

(X1?x2) ? (x2?3) ? (x3?x4) ? (x4?x5 ) = 1 (y1?y2) ?(y2?y3) ? (y3?y4) ? (y4?y5 ) = 1 y5?x5 =1 1-е уравнение (х) 2-е уравнение (у)

y5?x5 =1. Исключаем из общего решения у5?х5 = 0 (1?0) – 5 вариантов. Ответ: 6*6 - 5 = 31

7 В15

В15

(X1?x2) ? (x2?x3) ? (x3?x4) ? (x4?x5 ) = 1 (y1?y2) ? (y2?y3) ?(y3?y4) = 1 1-е уравнение (х) 2-е уравнение (у)

Уравнения не зависят друг от друга, количество решение равно 6*5 = 30 Ответ: 30.

8 В15

В15

(X1?x2) ? (x2?3) ? (x3?x4) ? (x4?x5 ) = 1 (y1?y2) ? (y2?y3) ? (y3?y4) ? (y4?y5 ) = 1 x2?y2 =0 х у

1-е и 2-е уравнения имеют по 6 решений, т.Е. 6*6=36

x2?y2 =0

Исключаем из общего решения x2?y2 = 0 (1?0) – 8 вариантов. Ответ: 36 – 8 = 28

Х1 х2 х3 х4 х5

Y1 y2 y3 y4 yх5

9 Декабрь 2013

Декабрь 2013

В15

Решения для 1-го и 2-го уравнений: 6*6=36

Исключаем из общего кол-ва решений х1 ?y1 = 0 (х1=1, y1=0) x2 ? y2 =0 (х2=1, y2=0)

Ответ: 36 - 9= 27

10 Решение: Не должно быть чередований – 10 Рассмотрим возможные варианты

Решение: Не должно быть чередований – 10 Рассмотрим возможные варианты

Ответ: 6 вариантов

11 В15

В15

Ответ: 2

(x5 ? x4) ? (x4 ? x3) ? (x3 ? x2) ? (x2 ? x1) ? (x1 ? x5 ) = 1 Выражение принимает значение 1, когда все сомножители = 1. Выражение (Х1 ? Х5) и выражение (Х5 ? Х4) связаны между собой переменной Х5. Перепишем для удобства уравнение в виде системы Первое уравнение имеет 6 решений: Только 2 решения из всех подходят для 2-го уравнения:

12 В15

В15

Сколько различных решений имеет логическое уравнение (¬X1 ? X2) ? (¬X2 ? X3) ? (¬X3 ? X4) ? (¬X4 ? X5) ? (¬X5 ? X6) = 1 перепишем уравнение, заменив знаки логических операций: заменяем все выражения в скобках на импликацию (см.теорию): Решениями этого уравнения будут все комбинации значений переменных Х1 .. Х6, для которых в соответствующей битовой цепочке нет последовательности 1 0;

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

13 В15

В15

Сколько существует различных наборов значений логических переменных Х1…Х6, У1… У6 которые удовлетворяют всем перечисленным ниже условиям? (Х1? Х2) ? (Х2? Х3) ? (Х3? Х4) ? (Х4? Х5) ? (Х5? Х6)=1 (У1? У2) ? (У2? У3) ? (У3? У4) ? (У4? У5) ? (У5? У6)=1 (?У1?Х1) ? (?У2?Х2) ? (?У3?Х3) ? (?У4?Х4) ? (?У5?Х5) ? (?У6?Х6) =1 В ответе указать количество наборов. Для 1 и 2 уравнений получаем по 7 наборов значений. Т.к. уравнения не зависят друг от друга, то общее кол-во решений = 7*7=49. Рассмотрим 3-е уравнение. (?У1?Х1) ? (?У2?Х2) ? (?У3?Х3) ? (?У4?Х4) ? (?У5?Х5) ? (?У6?Х6) =1 Его можно записать: (У1?Х1) ? (У2 ? Х2) ? (У3 ? Х3) ? (У4 ? Х4) ? (У5 ? Х5) ? (У6 ? Х6) =1 При подсчете количества наборов значений будем учитывать только те, которые удовлетворяют первым двум уравнениям.

14 Рассмотрим все значения Х отдельно: (У1

Рассмотрим все значения Х отдельно: (У1

Х1) ? (У2 ? Х2) ? (У3 ? Х3) ? (У4 ? Х4) ? (У5 ? Х5) ? (У6 ? Х6) =1 Все значения Х=1 - 7 наборов; Х1 = 0 – исключаем первую строку таблицы Y – 6 наборов; X1=X2=0 – исключаются 1 и 2 строки таблицы Y – 5 наборов; Х1=Х2=Х3=0 – 4 набора и т.д. Суммируем количество наборов значений 7+6+5+4+3+2+1 = 28 Ответ : 28 решений.

Y1

Y2

Y3

Y4

Y5

Y6

X1

X2

X3

X4

X5

X6

1

1

1

1

1

1

1

1

1

1

1

1

0

1

1

1

1

1

0

1

1

1

1

1

0

0

1

1

1

1

0

0

1

1

1

1

0

0

0

1

1

1

0

0

0

1

1

1

0

0

0

0

1

1

0

0

0

0

1

1

0

0

0

0

0

1

0

0

0

0

0

1

0

0

0

0

0

0

0

0

0

0

0

0

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

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

Х1…Х10, которые удовлетворяют всем перечисленным ниже условиям? ((Х1? Х2) ? (Х3? Х4)) ? (?(Х1? Х2) ? ?(Х3? Х4))=1 ((Х3? Х4) ? (Х5? Х6)) ? (?(Х3? Х4) ? ?(Х5? Х6))=1 . . . ((Х7? Х8) ? (Х9? Х10)) ? (?(Х7? Х8) ? ?(Х9? Х10))=1

Таблица истинности для эквивалентности:

Всего в системе уравнений используется пять пар переменных: Х1-Х2; Х3-Х4; Х5-Х6; Х7-Х8; Х9-Х10. Первая пара Х1-Х2 в первом уравнении дает 4 набора значений, которые удовлетворяют заданному условию: Х1=0, Х2=0 для первой части первого уравнения; Х1=1, Х2=1 для первой части первого уравнения; (Х1? Х2) Х1=0, Х2=1 для второй части первого уравнения; Х1=1, Х2=0 для второй части первого уравнения; ?(Х1? Х2)

0

0

1

0

1

0

1

0

0

1

1

1

Х1

Х2

Х1? х2

16 ((Х1? х2)

((Х1? х2)

(х3? х4)) ? (?(х1? х2) ? ?(х3? х4))=1 ((х3? х4) ? (х5? х6)) ? (?(х3? х4) ? ?(х5? х6))=1 . . . ((х7? х8) ? (х9? х10)) ? (?(х7? х8) ? ?(х9? х10))=1

Вторая пара Х3-Х4 в первом уравнении дает еще 4 набора значений (увеличивает количество в 2 раза). Х3=0, Х4=0 для первой части первого уравнения; Х3=1, Х4=1 для первой части первого уравнения; Х3=0, Х4=1 для второй части первого уравнения; Х3=1, Х4=0 для второй части первого уравнения; Причем, значения 1 и 2 скобок в обоих частях уравнения не должны совпадать.

Каждая следующая пара переменных увеличивает количество наборов в два раза. Общее количество наборов значений будет равно: 4 * 2 * 2 * 2 * 2 = 64 Х1-Х2 Х3-Х4 Х5-Х6 Х7-Х8 Х9-Х10

Х1

Х2

Х3

Х4

0

0

1

0

0

0

0

1

0

1

0

0

0

1

1

1

1

0

0

0

1

0

1

1

1

1

1

0

1

1

0

1

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

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

Х1…Х10, которые удовлетворяют всем перечисленным ниже условиям? ?(Х1? Х2) ? (Х3? Х4) =1 (?(Х3? Х4)? (Х5? Х6) =1 . . . ?(Х7? Х8) ? (Х9? Х10 )=1 Обозначим (Х1? Х2)=У1; (Х3? Х4)=У2; (Х5? Х6)=У3; (Х7? Х8)=У4; (Х9? Х10)= У5 Получим систему: ? У1 ? У2=1 ? У2 ? У3=1 ? У3 ? У4=1 ? У4 ? У5=1 Рассмотрим возможные наборы значений: Если У1=1, то У2, Y3, Y4 и Y5 должны быть равно только 1 – первый набор значений, т.к. при У1=1 других наборов нет. Рассмотрим возможные наборы вариантов:

18 Получаем еще 5 наборов значений, которые удовлетворяют преобразованной

Получаем еще 5 наборов значений, которые удовлетворяют преобразованной

системе. Вернемся к замене. Так как (Х1? Х2)=У1 (значение У зависит от значения двух величин) и так далее, то замена дает 25 наборов значений, то есть 32 решения. Общее количество наборов значений, которые удовлетворяют заданным условиям будет равно: 6*32=192

? У1 ? у2=1 ? у2 ? у3=1 ? у3 ? у4=1 ? у4 ? у5=1

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

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

Х1…Х10, которые удовлетворяют всем перечисленным ниже условиям? (Х2? Х1) ? (Х2 ? Х3) ?(?Х2 ??Х3) =1 (Х3? Х1) ? (Х3 ? Х4) ?(?Х3 ??Х4) =1 … (Х9? Х1) ? (Х9 ? Х10) ?(?Х9 ??Х10) =1 (Х10? Х1)=0 Упростим логическое выражение учитывая, что (Х2 ? Х3) ?(?Х2 ??Х3) = (Х2? Х3) Получим: (Х2? Х1) ? (Х2? Х3) =1 (Х3? Х1) ? (Х3? Х4) =1 … (Х9? Х1) ? (Х9? Х10) =1 (Х10? Х1)=0 Скобка дает значение 1, если значения логических величин совпадает. Рассмотрим сколько наборов удовлетворяют условию, если Х1=0

20 (Х2? Х1)

(Х2? Х1)

(Х2? Х3) =1 (Х3? Х1) ? (Х3? Х4) =1 … (Х9? Х1) ? (Х9? Х10) =1 (Х10? Х1)=0 Для Х1=0 получили 9 наборов значений логических величин. Для Х1=1 (симметрично Х1=0) будет также 9 наборов значений. Полное количество наборов значений для данной системы уравнений будет равно: 9*2=18

21 В15

В15

X4 = 1– ОДНО РЕШЕНИЕ; Х4=Х3=1 – 2-А РЕШЕНИЯ; Х4=Х3=Х2=1 – 3 РЕШЕНИЯ; Х4=Х3=Х2=Х2 =1 – 4 РЕШЕНИЯ; (Х4 ? Х5) И (Y4 ?Y5) = 1 по 6 решений ; Общее кол-во решений: 6+6+4+3+2+1=22

Решения для 1-го и 2-го уравнений

Рассмотрим последнее уравнение.

«Решение систем логических уравнений»
http://900igr.net/prezentacija/algebra/reshenie-sistem-logicheskikh-uravnenij-243021.html
cсылка на страницу

Системы уравнений

17 презентаций о системах уравнений
Урок

Алгебра

35 тем
Слайды
900igr.net > Презентации по алгебре > Системы уравнений > Решение систем логических уравнений