Информатика и математика, (для юристов), 2011. Информатика и математика проблемнотематический комплекс
 Скачать 3.34 Mb.
|
|
тождественными. Пример. Составим таблицу истинности следующей формулы: ( ) ( ) Z Y Y X → → & : X Y Z ( ) Y X → ( ) Z Y → ( ) ( Y Y X → → & ) Z 0 0 0 1 1 1 0 0 1 1 1 1 0 1 0 1 0 0 0 1 1 1 1 1 1 0 0 0 1 0 1 0 1 0 1 0 1 1 0 1 0 0 1 1 1 1 1 1 Всяки , вво логическую операцию, учитываем их свойства: й раз дя 0 & = A A – закон сключе ого про воречи и нн ти я; – закон третьего; исключенного 1 = ∨ A A законы идемпотентности: , A A A = & ; A A A = ∨ законы отрицания: B A B A ∨ = & , B A B A & = ∨ ; двойного отрицания: закон навешивания A A = ; закон контрапозиции: A B B A → = → Теперь выпишем законы Булевой алгебры: Ком Ассоциативный закон мутативный закон ( ) ( ) Z Y X Z Y X ∨ ∨ = ∨ ∨ X Y Y X ∨ = ∨ X Y Y X & & = ( ) ( ) Z Y X Z Y X & & & & = Z Y X & = ∨ Дистрибутивный закон Законы поглощения ( ) ( ) ( ) Z X Y X & & ∨ ( ) X X Y X = ∨ Z Y X = ∨ & & ( ) ( ) ( ) Z X Y X ∨ ∨ & ( ) X X Y X = ∨ & Выпишем приведенные ранее выражения операций через &, ∨,¬ ( ) ( ) ( ) ( ) B A A A B B A B A & & = → → = ↔ B & ∨ B A B A B A ∨ = == → & Информатика и математика 200 ( ) ( ) B A B A B A & & ∨ == ⊕ Методы упрощения логических выражений. Методы решения логических задач Рассмотрим пример решения логической задачи. Пример 1. После обсуждения состава участников экспедиции решено, что должны выполняться два условия: 1. Если поедет Арбузов, то должны ехать Брюквин или Вишневский. 2. Если поедут Арбузов и Вишневский, то поедет Брюквин. Составить логическую формулу принятия решения в символической форме, упростить полученную формулу и сформулировать по ней новое условие формирования экспедиции. Введем переменные и соответствующие им элементарные высказыва- ния. A – поедет Арбузов; Б – поедет Брюквин; В – поедет Вишневский. То формирования экспедиции будут выгля- деть сл ) улу и упростим выражение: гда выработанные условия едующим образом: 1. ( Б A ∨ → В 2. ( ) В Б A → & Составим общую форм ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) & & & & Б Б А Б В А В Б А Б В А В Б Б Б A = ∨ ∨ = ∨ ∨ ∨ ∨ = ∨ ∨ → ∨ → т.е. е Пример 2. & & А В A В ∨ = Б А А В В → = ∨ сли поедет Арбузов, то поедет Брюквин. По подозрению в совершенном преступлении задержаны Браун, Джон и Смит. Один из них – уважаемый в городе старик, второй – ходе следствия старик гово- . Преступник Смит ( ¬Б&С); новат Браун ( ¬С&Б). о и выражениями: Браун: чиновник, а третий – известный мошенник. В рил правду, мошенник лгал, а третий задержанный в одном случае говорил правду, а в другом лгал. Вот что они говорили: Браун: Я совершил это. Джон не виноват (Б& ¬Д); жон: Браун не виноват Д Смит: Я не виноват. Ви Опишем эти высказывания формально: Б – преступление совершил Браун; Д – преступление совершил Джон; С – преступление совершил Смит. Т им гда их слова описываются следующ ; Д Б & 2. План-конспект лекционного курса 201 Джон: C Б & ; Смит: Б С & Так как по условиям задачи две из этих & ложны и одна истинна, то ( ) ( ) ( ) Б С C Б Д & ∨ ∨ м таблицу истинности: Б L & & = Состави № Б Д С Д Б & Б С & L C Б & 1 0 0 0 0 0 0 0 2 0 0 1 0 1 0 1 3 0 1 0 0 0 0 0 4 0 1 1 0 1 0 1 5 1 0 0 1 0 1 1 6 1 0 1 1 0 0 1 7 1 1 0 0 0 1 1 8 1 1 1 0 0 0 0 1. Исключим рассмотрения те боры а которых по усло- вию задачи дна и – и нн ледо ельно из на , н 0 ( = L о з & сти а, с ват , 1 = L ), 1, 3, 8. 2. Исключим учай , та ак в м две истинны, что отиворе- чит условию задачи сл 5 к к не & пр 3. В случаях 4, 6, 7 у нас в начальном наборе две 1 , т.е. 2 преступни- ка, а по условию задачи он один. Остается только случай 2 , т.е. преступник Смит и оба его высказыва- ния ложны. 0 & = Б С , следовательно, Б – ложно и С – истинно; 1 & = C Б = 1 – Джон – уважаемый старик. Остается, что Браун – чиновник, и поскольку Б – ложно , то Д – ис- тинно. Пользуя у ры, можно упро- щать логичес носильные преобразования формул формул тождественным преобразованиям в ариф- мети сь законами и тождествами Б левой алгеб кие выражения. Рав Используя равносильности, можно часть формулы или всю формулу заменить равносильной ей формулой. Такие преобразования назы- ваются равносильными. (Аналог ке, алгебре и тригонометрии.) Равносильные преобразования используются для доказательства рав- носильностей, приведения формул к заданному виду, упрощения формул. Формула А считается проще равносильной ей формулы В, если она содержит меньше букв, меньше логических операций. При этом обычно Информатика и математика 202 опер скво им очередному шагу. ации эквивалентность и импликация заменяются операциями дизъ- юнкция и конъюнкция, а отрицание относят к элементарным высказываниям Для удобства использования и ссылок при проведении равносильных преобразований перечень наиболее часто употребляемых равносильностей (законов логических операций над высказываниями) можно свести в еди- ную таблицу, в которой рассмотренные выше равносильности даны в зной нумерации. При проведении равносильных преобразований каждый шаг основы- вается на использовании того или иного закона. Номер соответствующей формулы (из общей таблицы) мы будем указывать над знаком равносиль- ности, предшествующ Рассмотрим ряд примеров равносильных преобразований. Пример 1. Доказать равносильность y x y x y x ∧ ∨ ∧ ≡ ↔ ) ( ) ( ) ( ) ( ) ( ) ( 6 6 18 19 x y x y y x x y y x x y y x y x ≡ ∨ ∨ ∨ ≡ ∨ ∧ ∨ ≡ → ∧ → ≡ ↔ y x y ∧ ∨ 0 0 3 10 15 x x y y x x y y x x y y y x x y x ∧ ≡ ∧ ∨ ∧ ≡ ∧ ∨ ∨ ∨ ∧ ≡ ∧ ∨ ∧ ∨ ∧ ∨ ∧ ≡ Пример 2. Упростить формулу A y y x ≡ ∧ ∨ → ) y x ∨ ( y y y x y y x y x y y x y x A П ≡ ∧ ∨ ≡ ∧ ∨ ∨ ∨ ≡ ∧ ∨ ∨ ∨ ≡ ) ( ) ( ) ( 8 1 18 Предикаты я рассматриваются к нераздельные целы инности или ложности. Ни структура высказываний, ни тем более их содержание не затраги- вают ремя и в науке, и в практике используются заключения, суще тся как целые, неделимые, без учета их в ащее, хотя оно В алгебре логики высказывани ка е и только с точки зрения их ист ся. В то же в ственным образом зависящие как от структуры, так и от содержания используемых в них высказываний. Например, в рассуждении: «Всякий ромб – параллелограмм; АВСD – ромб; следовательно, АВСD – параллелограмм» – посылки и заключение являются элементарными высказываниями логики высказываний и с точ- ки зрения этой логики рассматриваю нутренней структуры. Следовательно, алгебра логики, будучи важной частью логики, оказывается недостаточной в анализе многих рассуждений. В связи с этим возникает необходимость в расширении логики выска- зываний, в построении такой логической системы, средствами которой можно было бы исследовать структуру тех высказываний, которые в рам- ках логики высказываний рассматриваются как элементарные. Такой логической системой является логика предикатов, содержащая всю логику высказываний в качестве своей части. Логика предикатов, как и традиционная формальная логика, расчленя- ет элементарное высказывание на субъект (буквально – подлеж может играть и роль дополнения) и предикат (буквально – сказуемое, хотя оно может играть и роль определения). 2. План-конспект лекционного курса 203 Субъект – это то, о чем что-то утверждается в высказывании; предикат – это то, что утверждается о субъекте. Например, в высказывании «7 – простое число», «7» – субъект, «про- стое число» – предикат. Это высказывание утверждает, что «7» обладает свой ретное число 7 пере- менн ния, а при других значениях х (напри- мер, ется обла- стью ством «быть простым числом». Если в рассмотренном примере заменить конк ой х из множества натуральных чисел, то получим высказывательную форму «х – простое число». При одних значениях х (например, х=13, х=17) эта форма дает истинные высказыва х=10, х=18) эта форма дает ложные высказывания. Ясно, что эта высказывательная форма определяет функцию одной переменной х, определенной на множестве N, и принимающую значения из множества {1;0}. Здесь предикат становится функцией субъекта и выража- ет свойство субъекта. Дадим несколько определений, относящихся к предикатам. Одноместным предикатом Р(x) называется произвольная функция переменного x, определенная на множестве M и принимающая значение из множества {1; 0}. Множество М, на котором определен предикат Р(x), называ определения предиката Р(x). Множество всех элементов M x ∈ , при которых предикат принимает значения «истина» (1), называет множеством (областью) истинности пред ся иката Р(x), т.е. множество истинности предиката Р(х) – это множест- во { } , 1 ) ( , : = ∈ = x P M x x I p или иначе: [ ] P M x , или так: [ ] ) (x P M x предикат Р(x) – «x – простое число» определен на множестве N, а множе- ство истинности I P для него есть множество всех простых чисел. Пр sinx=0» определен на множестве R, а его множест- вом ся . Так, например, едикат Q(x) – « истинности являет { } , k k I Q Z ∈ = π жеством исти меров видим что одноместные предикаты вы- раж ости совпадает с областью опре е М, называется тождест- венн Предикат F(x) – «диагонали параллелограмма x взаимно перпендику- лярны» определен на множестве всех параллелограммов, а его мно нности является множество всех ромбов. Из приведенных при , ают свойства предметов (субъектов). Предикат Р(х), определенный на множестве М, называется тождест- венно истинным, если его множество истинн деления, т. е. I p =M. Предикат Р(х), определенный на множеств о ложным, если его множество истинности является пустым множест- вом, т.е. I p =0. Информатика и математика 204 Естественным обобщением понятия одноместного предиката является понятие многоместного предиката, с помощью которого выражаются от- ношения между предметами. но может быть охарактеризовано высказыва- тель Примером бинарного отношения, т.е. отношения между двумя пред- метами, является отношение «меньше». Пусть это отношение введено на множестве Z целых чисел. О ной формой «х Z y x ∈ , , т.е. является функцией двух перемен- ных Р(х,y), определенной на множестве упорядоченных пар целых чисел ZхZ=Z 2 c множеством значений {1;0}. Двухместным предикат x,y) называется функция двух перемен- ных x и y, определенная на множестве М=М 1 хМ 2 и принимающая значения из множества {1;0}. ом Р( y» – предикат равенства, определенный на множестве ) – «х параллелен y»; ежащих на данной плоскости. ится понятие трехместного предиката. S(x,y,z) ращает его в двухместный пред ный предикат – это логическая (про- пози е операции над предикатами выск ых предикатов формируют- ся сл В числе примеров двухместных предикатов можно назвать такие пре- дикаты: • Q(x, y) – «x= RхR=R 2 ; • F(x,y • «прямая х параллельна прямой y», определенный на множестве прямых, л Совершенно аналогично ввод Приведем пример трехместного предиката (функции трех переменных): – «x+y=z». Подстановка в него х=3 прев икат: S(y,z) – «3+y=z», а подстановка х=3, z=2 – в одноместный пре- дикат S(y) – «3+y=2». Подстановка же S(2,3,5) превращает его в истинное высказывание, а S(1,7,4)– в ложное. Аналогично определяется и n-местный предикат (функция n перемен- ных). Пример п-местного предиката: R(x 1 , x 2 ,…,x n ): a 1 x 1 +…+a n x n =0, который, как видим, представляет собой алгебраическое уравнение с n неизвестными. При n=0 будем иметь нульмест циональная) переменная, принимающая значения из множества {1;0}. Логически Предикаты так же, как высказывания, могут принимать два значения: «истина» (1) и «ложь» (0), поэтому к ним применимы все операции логики азываний, в результате чего из элементарн ожные предикаты (как и в логике высказываний, где из элементарных высказываний формировались сложные, составные). Рассмотрим примене- ние операций логики высказываний к предикатам на примерах одномест- ных предикатов. Эти операции в логике предикатов сохраняют тот же смысл, который был им присвоен в логике высказываний. Пусть на некотором множестве M определены два предиката P(x) и Q(x). 2. План-конспект лекционного курса 205 Конъюнкцией двух предикатов P(x) и Q(x) называется новый (слож- ный) предикат ) ( ) ( x Q x P ∧ , который принимает значение «истина» при тех и толь ет зн ко тех значениях M x ∈ , при которых каждый из предикатов принима- ачение «истина», и принимает значение «ложь» во всех остальных случаях. Очевидно, что областью истинности предиката ) ( ) ( x Q x P ∧ является об- щая часть области истинности предикатов P(x) и Q(x), т.е. пересечение Q P I I ∩ Так, например, для предикатов P(x): «x – четное » и Q(x): x но 3» конъюнкцией ) ( ) ( x Q x P ∧ является предика ное число и x кратно 2», т.е. предикат «x делится на 6». число « крат т «x – чет имает зн предикатов принимает значение «лож Ясно, обла Дизъюнкцией двух предикатов P(x) и Q(x) называется новый предикат ) ( ) ( x Q x P ∨ , который прин ачение «ложь» при тех и только тех зна- чениях M x ∈ , при которых каждый из ь», и принимает значение «истина» во всех остальных случаях. что областью истинности предиката ) ( ) ( x Q x P ∨ является объе- динение сти истинности предикатов P(x) и Q(x), т.е. Q P I I ∪ й предикат Отрицанием предиката P(x) называется новы ) (x P или ) (x P , который принимает значение «истина» при всех значениях M x ∈ , при ко- торых предикат P(x) принимает значение «ложь», и принимает значение «ложь» при тех значениях M x ∈ , при которых предикат P(x) риним т значение «истина». Очевидно, что п ае P P I I = , т.е. множество истинности предиката ) (x P яв- ляется дополнением к множеству I P Импликацией п редикатов P(x) и Q(x) называется новый предикат x P явля x) принимает значение «истина», а Q(x) случаях. П ) (x Q → , который ется ложным при тех и только тех значениях M x ∈ , при которых одновременно P( ) ( – значение «ложь», и принимает значение “истина» во всех остальных оскольку при каждом фиксированном M x ∈ справедлива равносиль- ность ) ( ) ( ) ( ) ( 18 x Q x P x Q x P ∨ ≡ → , то Q P Q P I I I ∪ = → Эквиваленцией предикатов P(x) и Q(x) вается новый предикат ) ( ) ( x Q x P ↔ , который обращается в «истину всех тех и только тех M x ∈ , (x) о назы » при которых P(x) и Q бращаются оба в истинные или оба в лож- ные Для ег при высказывания. о множества истинности имеем: Q P Q P Q P I I I I I ∩ ∪ ∩ = ↔ |