Конспект_ОСНОВЫ ЛОГИКИ(3)(2). Решение логических задач. Учитель информатики Батракова Л. В
 Скачать 1.45 Mb.
|
|
7 ¬X 8 ) (X 9 X 10 ) (¬X 9 ¬X 10 ) = 1 где x 1 , x 2 , …, x 10 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов. 3.2. Уравнения и системы из задач прошлых лет 3.2.1. Логические уравнения 1. Определение решения логического уравнения. Можно решать такую задачу, составляя таблицу истинности для данного уравнения, но при большом количестве переменных это очень трудоемкая задача. Лучше решать задачу используя анализ или преобразование исходного выражения. Пример: Укажите значения переменных К, L, M, N, при которых логическое выражение (¬(М L) К) → (¬К ¬М N) ложно. Ответ запишите в виде строки из 4 символов: значений переменных К, L, М и N (в указанном порядке). Так, например, строка 1101 соответствует тому, что К=1, L=1, M=0, N=1. Решение (вариант 1, анализ исходного выражения): Конспект по теме: ‘Основы алгебры логики. Решение логических задач.’ Учитель информатики Батракова Л.В. 36 1) из формулировки условия следует, что выражение должно быть ложно только для одного набора переменных 2) из таблицы истинности операции «импликация» следует, что это выражение ложно тогда и только тогда, когда одновременно (¬(М L) К) =1и(¬К ¬М N)=0 3) первое равенство (логическое произведение равно 1) выполняется тогда и только тогда, когда 1 K и¬(М L)=1; отсюда следует М L =0 (логическая сумма равна нулю), что может быть только при 0 L M ; таким образом, три переменных мы уже определили 4) из второго условия, (¬К ¬М N)=0, при 1 K и 0 M получаем 0 N Ответ: 1000 Решение (вариант 2, упрощение выражения): 1) заменим импликацию по формуле А В = ¬ A ∨ B: ¬ (¬(М L) К) (¬К ¬М N)=0 2) раскроем инверсию сложного выражения по формуле де Моргана ¬ (A ∧ B) = ¬ A ∨ ¬ B : М L ¬К ( ¬К ¬М ) N=0 3) используя закон поглощения A ∨( A ∧ B) = A упростим выражение: ¬К (¬К ¬М )= ¬К: 4) мы получили уравнение M L ¬K N=0 , в нем все слагаемые должны быть равны нулю 5) поэтому сразу находим 1 , 0 K N L M Ответ: 1000 2. Определение количества решений логического уравнения. Этот тип задач, так же как и предыдущие задачи лучше решать путем логических рассуждений. Пример 1: Сколько различных решений имеет уравнение: (K L M) (¬L ¬M N) = 1 где K, L, M, N – логические переменные? В ответе не нужно перечислять все различные наборы значений K, L, M и N, при которых выполнено данное равенство. В качестве ответа Вам нужно указать количество таких наборов. Решение (поиск неподходящих комбинаций): 1) здесь используется сложение двух логических произведений, которое равно 1 если одно из двух слагаемых истинно 2) следовательно, исходное логическое уравнение можно представить в виде двух уравнений: K L M=1 ¬L ¬M N = 1 Достаточно, чтобы выполнялось хотя бы одно любое. 3) уравнение K L M=1 только в одном случае, если K=L=M=1, а N может принимать любые (логические) значения, то есть, 0 или 1; cледовательно, из первого уравнения получили два решения – 1110 и 1111 4) уравнение ¬L ¬M N=1такжеимеет два решения: требуется, чтобы 0 M L , 1 N , а K может быть равно 0 или 1; следовательно, из второго уравнения получили тоже два решения – 0001 и 1001 5) среди полученных четырех решений нет одинаковых, поэтому исходное уравнение имеет 4 решения Ответ: 4 Пример 2: Сколько различных решений имеет уравнение: Конспект по теме: ‘Основы алгебры логики. Решение логических задач.’ Учитель информатики Батракова Л.В. 37 ((K L ) (L M N)) = 0 где K, L, M, N – логические переменные? В ответе не нужно перечислять все различные наборы значений K, L, M и N, при которых выполнено данное равенство. В качестве ответа Вам нужно указать количество таких наборов. Решение: 1) так как импликация ложна только в одном случае, когда из истины следует ложь, следовательно исходное уравнение можно представить в виде двух уравнений: K L=1 L M N=0 2) первое уравнение равно 1 в трех случаях: {K=L=1}, {K=0, L=1}, {K=1, L=0} 3) рассмотрим возможные решения второго уравнения для всех трех случаях 4) для случаев {K=L=1} и {K=0, L=1}, т.к. L=1, а K – в уравнение не входит, то второе уравнение выполняется в трех случаях: {M=0,N=1}, {M=1,N=0}, {M=N=0} 5) для случая {K=1, L=0}, т.к. L=0, второе уравнение выполняется всегда , при любых значениях M и N, и таких вариантов может быть четыре: {M=N=0}, {M=N=1}, {M=1, N=0}, {M=0, N=1} 6) всего получилось десять различных вариантов ответов. Ответ: 10 3.2.2. Системы логических уравнений 3.Определение решения системы логических уравнений. Естьразличные способы решения систем логических уравнений. Это сведение к одному уравнению, построение таблицы истинности, декомпозиция, последовательное решение уравнений. Рассмотрим различные способы решения системы уравнений на одном примере. Замечание: Для сокращения записи будем использовать следующие обозначения: ¬ A А А В А + В А В А * В Пример: Решить систему логических уравнений: 1-й способ: сведение к одному уравнению. Данный способ предполагает преобразование логических уравнений, таким образом, чтобы правые их части были равны истинностному значению (то есть 1). Для этого применяют операцию логического отрицания. Затем, если в уравнениях есть сложные логические операции, заменяем их базовыми: «И», «ИЛИ», «НЕ». Следующим шагом объединяем уравнения в одно, равносильное системе, с помощью логической операции «И». После этого, следует сделать преобразования полученного уравнения на основе законов алгебры логики и получить конкретное решение системы. Решение: 1)Применяем инверсию к обеим частям первого уравнения: 2) Представим импликацию через базовые операции «ИЛИ», «НЕ»: 3) Поскольку левые части уравнений равны 1, можно объединить их с помощью операции “И” в одно уравнение, равносильное исходной системе: Конспект по теме: ‘Основы алгебры логики. Решение логических задач.’ Учитель информатики Батракова Л.В. 38 Раскрываем первую скобку по закону де Моргана и преобразовываем полученный результат: Полученное уравнение, имеет одно решение: A=0, B=0 и C=1. Ответ: A=0 B=0 C=1 2-й способ: построение таблиц истинности. Поскольку логические величины имеют только два значения, можно просто перебрать все варианты и найти среди них те, при которых выполняется данная система уравнений. То есть, мы строим одну общую таблицу истинности для всех уравнений системы и находим строку с нужными значениями. Решение: Составим таблицу истинности для системы: A B C 1 1 1 0 1 1 1 1 0 0 1 1 1 0 1 0 1 1 1 0 0 0 1 1 0 1 1 1 1 1 0 1 0 1 1 0 0 0 1 1 0 1 0 0 0 1 0 0 Выделена строчка, для которой выполняются условия задачи. Таким образом, A=0, B=0 и C=1. Ответ: A=0 B=0 C=1 3-й способ: декомпозиции. Идея состоит в том, чтобы зафиксировать значение одной из переменных (положить ее равной 0 или 1) и за счет этого упростить уравнения. Затем можно зафиксировать значение второй переменной и т.д. Решение: Пусть A = 0, тогда: Из первого уравнения получаем B=0, а из второго – С=1. Решение системы: A = 0, B = 0 и C = 1. Ответ: A=0 B=0 C=1 4-й способ: последовательное решение уравнений. На каждом шаге добавляется по одной переменной в рассматриваемый набор. Для этого необходимо преобразовать уравнения таким образом, что бы переменные вводились в алфавитном порядке. Далее строим дерево решений, последовательно добавляя в него переменные. Решение: 1) Первое уравнение системы зависит только от A и B, а второе уравнение от А и C. Переменная А может принимать 2 значения 0 и 1: 2) Из первого уравнения следует, что , поэтому при A = 0 получаем B = 0, а при A = 1 имеем B = 1. Итак, первое уравнение имеет два решения относительно переменных A и B. Конспект по теме: ‘Основы алгебры логики. Решение логических задач.’ Учитель информатики Батракова Л.В. 39 3) Изобразим второе уравнение, из которого определим значения C для каждого варианта. При A=1 импликация не может быть ложной, то есть вторая ветка дерева не имеет решения. При A=0 получаем единственное решение C = 1: Ответ: A=0 B=0 C=1 4. Определение количества решений системы логических уравнений. При решении таких задач используется последовательный метод решения уравнений, табличный метод и метод замены переменных. Суть последнего метода состоит в том, что сначала необходимо максимально упростить каждое из уравнений на основе законов алгебры логики, а затем заменить сложные части уравнений новыми переменными и определить количество решений новой системы. Далее вернуться к замене и определить для нее количество решений. Рассмотрим решение таких задач на примерах. Пример 1: Сколько различных решений имеет система уравнений ¬X 1 X 2 = 1 ¬X 2 X 3 = 1 ... ¬X 9 X 10 = 1 где x 1 , x 2 , …, x 10 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов. Решение (последовательное решение, через единицы): 1) количество комбинаций 10 логических переменных равно 2 10 = 1024, поэтому вариант с построением полной таблицы истинности отпадает сразу 2) сначала рассмотрим первое уравнение 1 2 1 X X ; согласно таблице истинности операции «ИЛИ» оно имеет 3 решения (точнее, с учетом других переменных, 3 группы решений): (0,0,*), (0,1,*) и (1,1,*); здесь звездочка означает, что остальные 8 переменных могут быть любыми 3) выпишем все решения в столбик, чтобы была видна закономерность: (0,0,*) (0,1,*) (1,1,*) 4) заметим, что при X 2 = 0 значение X 1 должно быть равно 0, а при X 2 = 1 значение X 1 может быть любым 5) второе уравнение, рассматриваемое отдельно, тоже имеет 3 группы решений: (x 1 ,0,0,*), (x 1 ,0,1,*) и (x 1 ,1,1,*), где x 1 , – некоторое логическое значение переменной X 1 6) решения системы первых двух уравнений – это те комбинации значений переменных, которые удовлетворяют одновременно и первому, и второму Конспект по теме: ‘Основы алгебры логики. Решение логических задач.’ Учитель информатики Батракова Л.В. 40 7) из п. 4 следует, что при X 2 = 0 значение X 1 должно быть равно 0, а при X 2 = 1 значение X 1 может быть любым, поэтому решение системы двух первых уравнений включает 4 группы: из (x 1 ,0,0,*) и (x 1 ,0,1,*) при X 1 = 0 получаем две группы (0,0,0,*) и (0,0,1,*) и из (x 1 ,1,1,*) получается еще две: (0,1,1,*) и (1,1,1,*). 8) таким образом, система из двух уравнений имеет 4 решения 9) выпишем все решения в столбик, чтобы была видна закономерность: (0,0,0,*) (0,0,1,*) (0,1,1,*) (1,1,1,*) 10) таким образом, если X 3 = 0, все предыдущие переменные определяются однозначно – они должны быть равны нулю (идем по системе «снизу вверх»); если же X 3 = 1, то предыдущие переменные могут быть любыми, второе уравнение их не ограничивает 11) поэтому при увеличении числа переменных на единицу количество решений также увеличивается на единицу 12) аналогично доказывается, что система из 3 уравнений имеет 5 решений, и т.д., то есть, система из 9 уравнений с 10 переменными имеет 11 решений Ответ: 11 Решение (последовательное решение, через нули): 1) сначала рассмотрим первое уравнение 1 2 1 X X ; согласно таблице истинности операции «ИЛИ» оно НЕ выполняется только в одном случае (точнее, с учетом других переменных, для одной группы комбинаций): (1,0,*) здесь звездочка означает, что остальные 8 переменных могут быть любыми 2) общее количество комбинаций X 1 и X 2 равно 2 2 = 4, поэтому число решений первого уравнения равно 4 – 1 = 3 3) второе уравнение, рассматриваемое отдельно, тоже ложно только для одной комбинации имеет 3 группы решений: (x 1 ,1,0,*), где x 1 , – некоторое логическое значение переменной X 1 4) теперь рассмотрим вместе первое и второе уравнения и определим, в скольких случаях хотя бы одно из них неверно 5) множества (1,0,x 3 ,*) и (x 1 ,1,0,*) не пересекаются, потому что в первом X 2 = 0, а во втором X 2 = 1, поэтому система из двух уравнений не выполнена для 4-х комбинаций: (1,0,0,*), (1,0,1,*), (0,1,0,*) и (1,1,0,*) 6) общее количество комбинаций трех логический переменных равно 2 3 = 8, поэтому количество решений системы из двух уравнений равно 8 – 4 = 4 7) аналогично доказывается, что система из 3 уравнений имеет 5 решений, и т.д., то есть, система из 9 уравнений с 10 переменными имеет 11 решений Ответ: 11 Решение (табличный метод): 1) рассмотрим все решения первого уравнения 1 2 1 X X по таблице истинности: 1 2 1 X X X 2 X 1 1 0 0 0 0 1 1 1 0 1 1 1 2) строчка, выделенная красным фоном, не удовлетворяет условию, поэтому дальше ее рассматривать не будем 3) теперь подключаем третью переменную и второе уравнение: X 3 X 2 X 1 ? 0 0 ? 1 0 Конспект по теме: ‘Основы алгебры логики. Решение логических задач.’ Учитель информатики Батракова Л.В. 41 ? 1 1 4) при каких значениях переменной X 3 будет верно условие 1 3 2 X X ? Очевидно, что на это уже не влияет X 1 (этот столбец выделен зеленым цветом). Если X 2 = 1, то сразу получаем, что X 3 = 1 (иначе 0 0 0 3 2 X X ): X 3 X 2 X 1 0 0 0 1 0 0 1 1 0 1 1 1 5) как видно из таблицы, верхняя строчка предыдущей таблицы (где были все нули) дает два решения при подключении очередного уравнения, а все остальные – по одному 6) понятно, что такая же ситуация будет продолжаться и дальше, то есть, при добавлении каждой новой переменной число решений увеличивается на 1 7) рассуждая таким образом и дальше, получаем, что для 3-х уравнений с 4-мя переменными будет 5 решений, для 4 уравнений – 6 решений, …, а для 9 уравнений – 11 решений 8) обратите внимание на форму таблицы – единицы и нули образуют два треугольника Ответ: 11 Пример 2: Сколько различных решений имеет система уравнений (X 2 X 1 ) (X 2 X 3 ) (¬X 2 ¬ X 3 )= 1 (X 3 X 1 ) (X 3 X 4 ) (¬X 3 ¬ X 4 )= 1 ... (X 9 X 1 ) (X 9 X 10 ) (¬X 9 ¬ X 10 )= 1 (X 10 X 1 ) = 0 где x 1 , x 2 , …, x 10 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов. Решение (табличный метод): 1) количество комбинаций 10 логических переменных равно 2 10 = 1024, поэтому вариант с построением полной таблицы истинности отпадает сразу 2) перепишем уравнения, используя более простые обозначения операций 1 ) ( 3 2 3 2 1 2 X X X X X X 1 ) ( 4 3 4 3 1 3 X X X X X X 1 ) ( 10 9 10 9 1 9 X X X X X X 0 1 10 X X 3) заметим, что по свойству операции эквивалентности ) ( 3 2 3 2 3 2 X X X X X X , поэтому уравнения можно переписать в виде 1 ) ( ) ( 3 2 1 2 X X X X 1 ) ( ) ( 4 3 1 3 X X X X 1 ) ( ) ( 10 9 1 9 X X X X 0 1 10 X X 4) первое уравнение выполняется, когда есть X 2 равно X 1 или X 3 5) по таблице истинности находим 6 вариантов (для удобства мы будем записывать сначала столбец для X 1 , а потом для всех остальных в обратном порядке): |