Лекции Русакова (1021002), страница 20
Текст из файла (страница 20)
Основные свойства булевых функций.Замечание.Для примеров, иллюстрирующих понятия функционально замкнутыхбулевыхфункций,атакжеполноты186системыбулевыхфункций,целесообразно рассмотреть все множество булевых функций от двухаргументов. Тем более, что эти булевы функции находят широкоепрактическое применение (табл. ниже).Таблица 5.04x1 0 0 1 1 Названиеx2 0 1 0 1f0f10 0 0 0Никогда0 0 0 1КонъюнкцияЗапретпо x2f20 0 1 0f3По0 0 1 1 вторение x1f40 1 0 0Запретпо x1АналитическоевыражениеОпределениеФункция привсехy = ( x1 ∨ x2 )( x1 ∨ x2 ) ⋅ комбинацияхаргумента⋅( x1 ∨ x2 )( x1 ∨ x2 )имеет нулевоезначение.Эта функцияпринимаетзначение 1только приy = x1x2истинностиобоихвысказываний.y = x1 x2y = x1 → x2 == x1 ∨ x2y = x1 x2 ∨ x1 x2 = x1y = x1 x2=y x2 → x1= x2 x1187Функцияповторяетзначение x1,если x2 = 0.Функцияповторяетзначение x1Функцияповторяетзначение x2,если x1 = 0.Примечаниеf5По0 1 0 1 вторение x20 1 1 0Сложениеf70 1 1 1Дизъюнкцияf8Отрицаниедизъюнк1 0 0 0ции(стрелкаПирса)f6f9Эквивавалент1 0 0 1лентностьf10Отрицание1 0 1 0 x2 илиинверсия x2y = x1 x2 ∨ x1x2 = x2Функцияповторяетзначение x2Функцияравна 1 тольков случаеy = x1 x2 ∨ x1 x2 =различного= x1 ⊕ x2значенияаргументов(искл.
“или”)Функцияравна 1 вслучаеy = x1 x2 ∨ x1 x2 ∨ x1x2 =истинности= x1 ∨ x2хотя быодноговысказыванияy = x1 x2 = x1 ∨ x2 == x1 ↓ x2y =x1 x2 ∨ x1 x2 == x1 ⇔ x2 = x1 ⊕ x2y = x1 x2 ∨ x1 x2 = x2188Функцияравна 1 тольков случаеложности всехвысказываний.Функцияравна 1 толькоприодинаковыхзначенияхаргументов.Функцияпринимаетзначениепротивоположное x2f11Имплика1 0 1 1ция отx2 к x1f12Ин1 1 0 0 версияx1f13Имплика1 1 0 1ция отx1 к x214Отрицаниеконъюнк1 1 1 0ции(штрихШеффера)1 1 1 1 Всегда15y = x2 ⇒ x1 = x1 ∨ x2Функцияравна 0 ⇔ x2 =1 и x1 = 0y = x1 x2 ∨ x1x2 = x1Функцияпринимаетзначениепротивоположное x1y = x1 ∨ x2 = x1 ⇒ x2Функцияравна 0 ⇔ x1 =1 и x2 = 0y = x1 ∨ x2 = x1 x2 == x1 | x2Функцияравна 0 ⇔истинны обааргументаy = x1 x2 ∨ x1x2 ∨∨ x1 x2 ∨ x1 x2Функциявсегдапринимаетзначение 1Глава 6.
Элементы теории доказательств.1896.01. Естественная дедукция.Логическиерассуждениях,заключения,определяютсякоторыерядомиспользуютлюдивэлементарныхсвоихправил,сформулированных ещё Аристотелем. Формализация этих правил приводит кразличным формальным системам для логических языков.Определение.Формальная система для языка логики предикатов первого порядка,называется естественной дедукцией (natural deduction).Определение.Задача формулирования системы естественной дедукции состоит вформализации процесса логических рассуждений, таким образом, каким онпредставляется нам и каким образом он для нас выглядит убедительным.Работы в этом направлении начинал ученик Лукасевича Ясковский, нопервую общепринятую систему естественной дедукции в 1935 годупредложил в своей диссертации Генцен.Аксиом в естественной дедукции нет, а правила вывода можноразделить на две группы: правила введения (обозначаются буквой i —«introduce»—слевасоответствующийзначокотсутствует,справаприсутствует), и правила исключения (обозначаются буквой е —«eliminate»,справасоответствующийзначокотсутствует,слеваприсутствует) для каждого логического значка и квантора (∨,∧, →, ¬, ∀, ∃) .190В теории доказательств общепринята запись правил вывода не только встрочной форме, но и в вертикальной форме дерева, поэтому в определенияхправил вывода мы будем выписывать обе формы их представления.(e1 ) исключение «и»A∧ B├ AA∧ BA(e2 ) исключение «и»A∧ B├BA∧ BBA, B ├ A ∧ BA BA∧ B(∧ i1 ) введение «и»(∨ i1 ) введение «или» слеваA├ A ∨ B(∨ i 2 ) введение «или» справаA├ B ∨ AAA∨ BAB∨ A[A]1 [B]1(∨ e ) исключение «или»Если A ├ C и B ├ C ,CCCB∨ Aто A ∨ B ├ CПоследнее правило можно прочесть так: если С доказано сиспользованием допущения А, и С доказано с использованием допущения В,и при этом мы знаем, что верно A ∨ B , то можно считать доказанным С (ужебез предположений о верности A и В).В последнем правиле использовалось следующее обозначение: посылкав квадратных скобках означает, что её можно исключить из рассмотрения.Можно представить себе это как «обрывание» листьев дерева вывода,соответствующих тем посылкам, которые можно исключить.
Индексомоколо квадратных скобок показывается то место в дереве, где «оборванныйлист» был использован (то есть посылки, заключенные в квадратные скобки,191стали ненужными). Дерево вывода можно читать так: необорванные листьядоказывают корень.Запись в виде дерева весьма компактна, но не всегда легко читаема.Зато запись в строчку (с подробными комментариями), как правило, легкочитается, но редко получается компактной.(→ e ) правило исключения импликацииA, A → B ├ BA A→ BB[A]1(→ i ) правило введения импликацииесли A ├ B ,B 1A→ Bто ├ A → BОпределение.Правило исключения импликации A, A → B ├ B называется modusponens.Это правило — настоящий камень преткновения для теориидоказательств.
Дело в том, что при помощи этого правила можно фактическизаменять одну формулу на любую другую, из неё вытекающую. Еслибольшинство других правил применимы только в определённых ситуациях, ивариантов их применения обычно не очень много, то modus ponens можноприменять практически всегда, и невозможно угадать, на какую именноформулу В нужно сейчас заменить формулу А. Это свойство modus ponensделает его очень сложным для автоматизации: как объяснить компьютеру,когда применять modus ponens?Поэтому логики неоднократно пытались либо удалить modus ponens издоказательств вообще, либо как-нибудь его ограничить, чтобы его можно192было автоматизировать; такие попытки называются общим термином cutelimination.Обратимся к правилам, имеющим дело с логическим значкомотрицания.
Введём псевдоформулу ⊥ «ложь», истинностное значениекоторой во всех интерпретациях будем считать нулём (можно было бывместо неё считать ложью, например, A( x ) ∧ ¬A( x ) для какой-нибудьпредметной переменной х и какого-нибудь предиката А). С помощью такойпсевдоформулыможно,например,легкозаписатьпротиворечивостьмножества формул Г следующим образом:Г╞⊥Теперь можно сформулировать правила для значка отрицания иконстанты «ложь»:(⊥е) правило исключения ⊥ ⊥ ├ A╧AЭто правило допускает простую интерпретацию: из лжи следует всечто угодно (ex falsum sequitor quodlibet). Поскольку в явном виде этотлогический принцип впервые сформулировал Иоанн Дуне Скот, его иногданазывают «правилом Дунса Скота».(⊥i)правило введения константы «ложь» ¬A, A ├ ⊥¬A A⊥[A]1( ¬ i)правило введения отрицания193Если ¬A ├⊥, то ├ ¬A⊥ 1¬A[A]1(RAA) правило сведения к противоречию Если ¬A ├⊥, то ├ A⊥ 1¬A(reductio ad absurdum)Замечание.Правило Дунса Скота (⊥е) в приведённой системе лишнее: оно следуетиз (RAA) и других правил; а вот если от (RAA) отказаться, то правило (⊥е)уже будет совершенно необходимо.6.02.
Метод математической индукции.Метод математической индукции ММИ лежит в основе доказательстваогромного числа теорем в различных разделах дискретной математики.Буквой N обычно обозначается множество натуральных чисел:N = {1,2,3,..., n,...}.N 0 – расширенное множество натуральных чисел, то естьN 0 = {0,1,2,3,..., n,...}.Пусть P(n ) обозначает некоторое свойство натуральных чисел.Теорема 1 (стандартный ММИ)Пусть свойство P верно при n = 1 и пусть из истинности P при n = kследует его истинность при n = k + 1 .
Тогда свойство P верно для любогоn∈ N .Определение.194Символом n! обозначается факториал произведение n!= 1 ⋅ 2 ⋅ ⋅ n , гдеn ∈ N . Например, 5!= 1 ⋅ 2 ⋅ 3 ⋅ 4 ⋅ 5 = 120 . По определению полагают 0!= 1 .Теперь сформулируем несколько утверждений, эквивалентных ММИ.Теорема 2Пусть множество A ⊆ N обладает следующими свойствами.1. 1∈ A .2. Для любого k ∈ N , если k ∈ A , то k + 1 ∈ A .Тогда A = N .Теорема 3 (возвратный ММИ)Пусть свойство Р(n) выполняется при n=1 и из того, что оно верно длялюбого k < n , следует, что Р верно при n. Тогда Р верно при любомнатуральном n.И последнее. Индуктивный процесс не обязан начинаться с 1.
Вкачестве базиса индукции может выступать любое целое число a.Теорема 4Пусть свойство P(n) выполняется при n=a и из истинности его длялюбого k ≥ a следует истинность для k+1. Тогда P(n) истинно для любогоцелого n ≥ a .6.03. Доказательствоматематическойнеравенствиндукции.Буняковского.195методомНеравенствоКоши-Теорема 1 (неравенство Коши-Буняковского)Для любых чисел a1 ,..., a n , b1 ,..., bn(a1b1 + a 2 b2 + ... + a n bn )2 ≤ (a1 2 + ... + a n 2 )(b1 2 + ...
+ bn 2 ).Доказательство22 2При n = 1 неравенство (a1b1 ) ≤ a1 b1 верно. Допустим,(a1b1 + a 2 b2 + ... + a k bk )2(≤ a1 + ... + a k22)(b21)+ ... + bk .2Докажем, что(a1b1 + ... + a k bk(+ a k +1bk +1 ) ≤2)()≤ a1 + ... + a k + a k +1 b1 + ...bk + bk +1 .222222Перепишем это неравенство, частично раскрыв скобки:(a1b1 + ... + a k bk )2 + 2a k +1bk +1 (a1b1 + ... + a k bk ) + a k +12 bk +12 ≤(≤ a1 + ...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
