Математическая логика и теория алгоритмов. Тическая логика и теория алгоритмов
 Скачать 453.81 Kb.
|
|
Контрольная работа по дисциплине Математическая логика и теория алгоритмов Выполнил: ст. гр. БИСЗ20- 01 Бурдыкин А.Г Проверил: доцент каф. ВМ Сливина Т. А. Вариант 3 1. Приведите примеры предложений а) являющихся высказываниями, б) не являющихся высказываниями. Решение. Высказывание в математической логике – это повествовательное предложение, выражающее суждение. Это суждение должно принимать определённое логическое значение – быть истинным или ложным. Примеры высказываний: 1) “Число 18 делится на 6” – это простое высказывание, которое имеет значение “истина”. 3) “Если число делится на 6, то оно делится на 3” – это сложное высказывание, которое имеет значение “истина”, оно состоит из двух простых высказываний “число делится на 6” и “число делится на 3”, которые связываются между собой импликацией (логическим следованием). 3) “Земля вращается вокруг Луны” – это ложное высказывание. Следующие предложения не являются высказываниями”: 1) “Который час?” – это вопросительное предложение, оно не является суждениям, которое имеет определённое значение истинности. 2) “Число 𝑥 меньше 7.” – относительно истинности этого предложения ничего нельзя сказать определённого, зависит от конкретного значения числа 𝑥. 3) “Да будет свет!” – восклицательное предложение, которое также не имеет определённого логического значения. 2. Определить логические значения высказываний при 𝑥 = 1, 𝑦 = 1, 𝑧 = 0. а) (𝑥⋀𝑦) ⟷ (𝑧⋁𝑦̅) б) ((𝑥⋁𝑦)⋀𝑧) ⟷ ((𝑥⋀𝑧)⋁(𝑦⋀𝑧)) Решение. а) (𝑥⋀𝑦) ⟷ (𝑧⋁𝑦̅) Конъюнкция 𝑥⋀𝑦 принимает значение 1 (истина) только в случае одновременной истинности 𝑥 и 𝑦, значит при 𝑥 = 1, 𝑦 = 1 𝑥⋀𝑦 = 1. Отрицание 𝑦̅ меняет значение истинности 𝑦 на противоположное, значит, 𝑦̅ = 0при 𝑦 = 1. Дизъюнкция 𝑧⋁𝑦̅ принимает значение 0 (ложь) только в случае одновременной ложности 𝑧 и 𝑦̅, значит 𝑧⋁𝑦̅ = 0 при 𝑧 = 0, 𝑦̅ = 0. Эквиваленция принимает значение 1 (истина) только в случае совпадения логических значений операндов. Значит при 𝑥⋀𝑦 = 1 и 𝑧⋁𝑦̅ = 0 значение (𝑥⋀𝑦) ⟷ (𝑧⋁𝑦̅) – ложь: (𝑥⋀𝑦) ⟷ (𝑧⋁𝑦̅) = 0. б) ((𝑥⋁𝑦)⋀𝑧) ⟷ ((𝑥⋀𝑧)⋁(𝑦⋀𝑧)) Дизъюнкция 𝑥⋁𝑦 принимает значение 0 (ложь) только в случае одновременной ложности 𝑧 и 𝑦, значит 𝑥⋁𝑦 = 1 при 𝑥 = 1, 𝑦 = 1. Конъюнкция (𝑥⋁𝑦)⋀𝑧 принимает значение 1 (истина) только в случае одновременной истинности 𝑥⋁𝑦 и 𝑧, значит (𝑥⋁𝑦)⋀𝑧 = 0 при 𝑥⋁𝑦 = 1, 𝑧 = 0. Аналогично, 𝑥⋀𝑧 = 0 при 𝑥 = 1, 𝑧 = 0 и 𝑦⋀𝑧 = 0 при 𝑦 = 1, 𝑧 = 0. Дизъюнкция (𝑥⋀𝑧)⋁(𝑦⋀𝑧) принимает значение 0 (ложь) только в случае одновременной ложности 𝑥⋀𝑧 и 𝑥⋀𝑧, значит (𝑥⋀𝑧)⋁(𝑦⋀𝑧) = 0 при 𝑥⋀𝑧 = 0 и 𝑦⋀𝑧 = 0. Эквиваленция принимает значение 1 (истина) только в случае совпадения логических значений операндов. Значит при (𝑥⋁𝑦)⋀𝑧 = 0 и (𝑥⋀𝑧)⋁(𝑦⋀𝑧) = 0 значение ((𝑥⋁𝑦)⋀𝑧) ⟷ ((𝑥⋀𝑧)⋁(𝑦⋀𝑧)) – истина: ((𝑥⋁𝑦)⋀𝑧) ⟷ ((𝑥⋀𝑧)⋁(𝑦⋀𝑧)) = 1 Заметим, что заданное высказывание всегда истинно – при любых значениях логических переменных, так как выражает закон дистрибутивности конъюнкции относительно дизъюнкции: (𝑥⋁𝑦)⋀𝑧 = (𝑥⋀𝑧)⋁(𝑦⋀𝑧). 3. Доказать равносильность формулы 𝑥 ⟶ (𝑦 ⟶ 𝑧) ≡ 𝑥⋀𝑦 ⟶ 𝑧 Решение. Докажем равносильность формулы двумя способами: с помощью таблиц истинности и с помощью равносильных преобразований. Составляем таблицу истинности для формулы 𝑥 ⟶ (𝑦 ⟶ 𝑧). Учитываем, что импликация ложна только в случае, когда из истины следует ложь. 𝑥 𝑦 𝑧 𝑦 ⟶ 𝑧 𝑥 ⟶ (𝑦 ⟶ 𝑧) 0 0 0 1 1 0 0 1 1 1 0 1 0 0 1 0 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 0 0 0 1 1 1 1 1 Теперь составляем таблицу истинности для формулы 𝑥⋀𝑦 ⟶ 𝑧. Учитываем, что конъюнкция истинна только в случае, когда оба операнда истинны. 𝑥 𝑦 𝑧 𝑥⋀𝑦 𝑥⋀𝑦 ⟶ 𝑧 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 1 1 0 1 1 0 0 0 1 1 0 1 0 1 1 1 0 1 0 1 1 1 1 1 Видим, что таблицы истинности для формул 𝑥 ⟶ (𝑦 ⟶ 𝑧) и 𝑥⋀𝑦 ⟶ 𝑧 совпадают, значит они равносильны (или вся формула равносильна): 𝑥 ⟶ (𝑦 ⟶ 𝑧) ≡ 𝑥⋀𝑦 ⟶ 𝑧 Другой способ доказательства: используем равносильные преобразования. 𝑥 ⟶ (𝑦 ⟶ 𝑧) ≡ [заменыем импликацию по закону 𝐴 ⟶ 𝐵 = 𝐴̅⋁𝐵] ≡ ≡ 𝑥̅⋁(𝑦̅⋁𝑧) ≡ 𝑥̅⋁𝑦̅⋁𝑧 𝑥⋀𝑦 ⟶ 𝑧 ≡ 𝑥⋀𝑦 ̅̅̅̅̅̅⋁𝑧 ≡ [используем закон де Моргана] ≡ (𝑥̅⋁𝑦̅)⋁𝑧 ≡ 𝑥̅⋁𝑦̅⋁𝑧 Отсюда: 𝑥 ⟶ (𝑦 ⟶ 𝑧) ≡ 𝑥⋀𝑦 ⟶ 𝑧 4. Составить РКС (схему): 𝐹(0,0,1) = 𝐹(0,1,1) = 𝐹(1,0,1) = 𝐹(1,1,1) = 1 Решение. Нам заданы наборы функции от трёх логических переменных 𝑥, 𝑦, 𝑧, на которых функция принимает значение 1. По этим данным составляем совершенную дизъюнктивную нормальную форму – СДНФ: в каждой элементарной конъюнкции этой формы переменная входит с отрицанием, если в соответствующем наборе она принимает значение 0: 𝐹 = 𝑥̅𝑦̅𝑧⋁𝑥̅𝑦𝑧⋁𝑥𝑦̅𝑧⋁𝑥𝑦𝑧 Сначала составим РКС для этой формы, затем упростим форму и составим РКС для упрощённой формы. Каждую элементарную конъюнкцию в этой форме представляем тремя последовательно соединёнными элементами (последовательное соединение соответствует логическому умножению - конъюнкции), которые соответствуют переменным в конъюнкции, а все эти тройки элементов соединяются параллельно (соответствует дизъюнкции – логическому сложению): Теперь упростим полученную форму СДНФ: 𝑥̅𝑦̅𝑧⋁𝑥̅𝑦𝑧 = [используем закон дистрибутивности] = 𝑥̅𝑧(𝑦̅⋁𝑦) = = [используем закон исключённого третьего] = 𝑥̅𝑧 ∙ 1 = = [используем закон единицы] = 𝑥̅𝑧 Аналогично, 𝑥𝑦̅𝑧⋁𝑥𝑦𝑧 = 𝑥𝑧(𝑦̅⋁𝑦) = 𝑥𝑧 ∙ 1 = 𝑥𝑧 Получаем: 𝐹 = 𝑥̅𝑧⋁𝑥𝑧 = (𝑥̅⋁𝑥)𝑧 = 1 ∙ 𝑧 = 𝑧 В итоге получаем упрощённую формулу для 𝐹: 𝐹 = 𝑧 Релейно-контактная схема для 𝐹 = 𝑧: 𝑥̅ 𝑥̅ 𝑥 𝑥 𝑦̅ 𝑦̅ 𝑦 𝑦 𝑧 𝑧 𝑧 𝑧 𝑧 5. Найти СДНФ и СКНФ: а) с помощью равносильных преобразований; б) с помощью таблицы истинности. (𝑥⋁𝑧̅) ⟶ 𝑦⋀𝑥 Решение. а) (𝑥⋁𝑧̅) ⟶ 𝑦⋀𝑥 = [заменяем импликацию по закону 𝐴 ⟶ 𝐵 = 𝐴̅⋁𝐵] = = (𝑥⋁𝑧̅ ̅̅̅̅̅)⋁(𝑦⋀𝑥) = [используем закон де Моргана] = = (𝑥̅⋀𝑧̿)⋁(𝑦⋀𝑥) = [ снимаем двойное отрицание и используем закон коммутативности ] = = (𝑥̅⋀𝑧)⋁(𝑥⋀𝑦) Получили дизъюнктивную нормальную форму. Из неё получим СДНФ – совершенную дизъюнктивную нормальную форму, используя закон единицы, закон исключенного третьего и закон дистрибутивности. 𝑥̅⋀𝑧 = 𝑥̅⋀1⋀𝑧 = 𝑥̅⋀(𝑦⋁𝑦̅)⋀𝑧 = 𝑥̅⋀𝑦⋀𝑧⋁𝑥̅⋀𝑦̅⋀𝑧 𝑥⋀𝑦 = 𝑥⋀𝑦⋀1 = 𝑥⋀𝑦⋀(𝑧⋁𝑧̅) = 𝑥⋀𝑦⋀𝑧⋁𝑥⋀𝑦⋀𝑧̅ Получаем СДНФ (знаки конъюнкции опустим): 𝑥̅𝑦𝑧⋁𝑥̅𝑦̅𝑧⋁𝑥𝑦𝑧⋁𝑥𝑦𝑧̅ Форму СКНФ получим из найденной формы (𝑥̅⋀𝑧)⋁(𝑥⋀𝑦): (𝑥̅⋀𝑧)⋁(𝑥⋀𝑦) = [ставим двойное отрицание] = = (𝑥̅⋀𝑧)⋁(𝑥⋀𝑦) ̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿ = [используем закон де Моргана] = = (𝑥̅⋀𝑧 ̅̅̅̅̅)⋀(𝑥⋀𝑦 ̅̅̅̅̅̅) ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅ = (𝑥⋁𝑧̅)⋀(𝑥̅⋁𝑦̅) ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅ = [закон дистрибутивности] = = (𝑥⋀𝑥̅)⋁(𝑥⋀𝑦̅)⋁(𝑧̅⋀𝑥̅)⋁(𝑧̅⋀𝑦̅) ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅ = 0⋁(𝑥⋀𝑦̅)⋁(𝑧̅⋀𝑥̅)⋁(𝑧̅⋀𝑦̅) ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅ = = (𝑥⋀𝑦̅)⋁(𝑥̅⋀𝑧̅)⋁(𝑦̅⋀𝑧̅) ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅ = [используем закон де Моргана] = = (𝑥⋀𝑦̅ ̅̅̅̅̅̅)⋀(𝑥̅⋀𝑧̅ ̅̅̅̅̅)⋀(𝑦̅⋀𝑧̅ ̅̅̅̅̅) = [ используем закон де Моргана и снимаем двойное отрицание ] = = (𝑥̅⋁𝑦)⋀(𝑥⋁𝑧)⋀(𝑦⋁𝑧) Получили КНФ. Из неё получим СКНФ, используя законы нуля, противоречия и закон дистрибутивности. 𝑥̅⋁𝑦 = (𝑥̅⋁𝑦)⋁0 = (𝑥̅⋁𝑦)⋁(𝑧⋀𝑧̅) = (𝑥̅⋁𝑦⋁𝑧)⋀(𝑥̅⋁𝑦⋁𝑧̅) Аналогично, 𝑥⋁𝑧 = (𝑥⋁𝑦⋁𝑧)⋀(𝑥⋁𝑦̅⋁𝑧) и 𝑦⋁𝑧 = (𝑥⋁𝑦⋁𝑧)⋀(𝑥̅⋁𝑦⋁𝑧) Учитывая каждую дизъюнкцию только один раз, получаем СКНФ: (𝑥̅⋁𝑦⋁𝑧)⋀(𝑥̅⋁𝑦⋁𝑧̅)⋀(𝑥⋁𝑦⋁𝑧)⋀(𝑥⋁𝑦̅⋁𝑧) б) Найдём СДНФ и СКНФ с помощью таблицы истинности. Составляем таблицу истинности для формулы (𝑥⋁𝑧̅) ⟶ 𝑦⋀𝑥. 𝑥 𝑦 𝑧 𝑧̅ 𝑥⋁𝑧̅ 𝑦⋀𝑥 (𝑥⋁𝑧̅) ⟶ 𝑦⋀𝑥 0 0 0 1 1 0 0 0 0 1 0 0 0 1 0 1 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 1 1 0 0 1 0 1 0 1 0 0 1 1 0 1 1 1 1 1 1 1 0 1 1 1 СДНФ составляется по наборам переменных, на которых функция принимает значение 1: в каждую элементарную конъюнкцию переменная входит с отрицанием, если в наборе она принимает значение 0: 𝑥̅𝑦̅𝑧⋁𝑥̅𝑦𝑧⋁𝑥𝑦𝑧̅⋁𝑥𝑦𝑧. СКНФ составляется по наборам переменных, на которых функция принимает значение 0: в каждую элементарную дизъюнкцию переменная входит с отрицанием, если в наборе она принимает значение 1: (𝑥⋁𝑦⋁𝑧)⋀(𝑥⋁𝑦̅⋁𝑧)⋀(𝑥̅⋁𝑦⋁𝑧)⋀(𝑥̅⋁𝑦⋁𝑧̅) Получили такие же формы СДНФ и СКНФ, только с перестановкой членов. 6. Записать на языке логики предикатов: а) “Из перпендикулярности векторов 𝑎 и 𝑏 следует равенство нулю их скалярного произведения”, б) “Если 𝑎 и 𝑏 делятся на 𝑐, то (𝑎 − 𝑏) и (𝑎 + 𝑏) делятся на 𝑐”. Решение. а) Вводим два 2-местных предиката, определённых на множестве пар векторов: 𝑃(𝑎, 𝑏) − "векторы 𝑎 и 𝑏 перпендикулярны" 𝑄(𝑎, 𝑏) − "скалярное произведение векторов 𝑎 и 𝑏 равно нулю" Тогда заданное высказывание с использованием импликации и кванторов общности для двух переменных имеет вид: ∀𝑎∀𝑏(𝑃(𝑎, 𝑏) ⟶ 𝑄(𝑎, 𝑏)) а) Вводим 2-местный предикат, определённый на множестве пар целых чисел 𝑍 × 𝑍: 𝑃(𝑎, 𝑏) − "𝑎 делится на 𝑏" Вводим два 3-местных предиката, определённых на множестве троек целых чисел 𝑍 × 𝑍 × 𝑍: 𝑄(𝑎, 𝑏, 𝑐) − "𝑎 − 𝑏 делится на 𝑐" 𝑅(𝑎, 𝑏, 𝑐) − "𝑎 + 𝑏 делится на 𝑐" Тогда заданное высказывание с использованием конъюнкций, импликации и кванторов общности для трёх переменных имеет вид: ∀𝑎∀𝑏∀𝑐(𝑃(𝑎, 𝑐)⋀𝑃(𝑏, 𝑐) ⟶ 𝑄(𝑎, 𝑏, 𝑐)⋀𝑅(𝑎, 𝑏, 𝑐)) 7. Изобразите на координатной плоскости область истинности предиката (𝑥 ≥ 2 ̅̅̅̅̅̅̅)⋀(𝑥 ≤ 𝑦) Решение. Область истинности предиката "𝑥 ≥ 2", определённого на множестве точек координатной плоскости – полуплоскость, лежащая правее прямой 𝑥 = 2 (включая точки прямой, т.к. неравенство нестрогое). Область истинности отрицания этого предиката 𝑥 ≥ 2 ̅̅̅̅̅̅̅ – это область истинности предиката 𝑥 < 2 - полуплоскость, лежащая левее прямой 𝑥 = 2 (исключая точки прямой, т.к. неравенство строгое). Область истинности предиката "𝑥 ≤ 𝑦", определённого на множестве точек координатной плоскости – полуплоскость, лежащая выше прямой 𝑦 = 𝑥 (включая точки прямой, т.к. неравенство нестрогое). Берём пересечение этих областей (так как предикаты 𝑥 ≥ 2 ̅̅̅̅̅̅̅ и 𝑥 ≤ 𝑦 соединены конъюнкцией) – получаем область истинности заданного предиката (заштрихована на рисунке, это неограниченная область): 𝑥 𝑦 0 2 𝑦 = 𝑥 |