Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Законы логики.

Не нашел

1.закон двойного отрицания:

2.законы идемпотентности:

3.законы коммутативности:

4.законы ассоциативности:

5.законы дистрибутивности:

6.законы поглощения:

7.законы де Моргана:

8.закон исключения импликации:

9.закон исключения эквиваленции:

10.закон контрапозиции:

11.законы исключенного третьего и противоречия:

12.законы нуля и единицы:

4. Пусть формула алгебры высказываний содержит только три операции: . Ф-лу F^* будем называть двойственной к ф-ле F, если она получена из F заменой каждой операции на двойственную, а именно: .

Закон двойственности. Пусть F-формула алгебры высказываний, не содержащая операции , , тогда имеет место след равносильность: .

Док-во: проведем используя ММИ по числу операций, входящих в заданную формулу: 1)Проверим, что указанная теорема вып-ся при n=1, т.е. если ф-ла содержит одну операцию: а)пусть ф-ла содержит только отрицание . б) в) вып-ся аналогично. 2)Предположим, что теорема выполнена для ф-л , содержащих не более k операций. 3)Покажем справедливость теоремы в случае, когда кол-во операций n=k+1 и формула F выражается через . Возможны 3 случая: а) . Док-во: а) (. б) (. в) (.

Критерий двойственности. Две формулы титт, когда равносильны двойственные им формулы. Док-во: .Пусть , тогда согласно определению отрицания и понятию равносильности: , след-но, согласно теореме ( и ( и ( ( В последней равносильности переименуем переменные, а именно, заменим на саму переменную, от этого равносильность не изменится, а значит мы получим .

5. Рассмотрим мн-во М, содержащее конечное число элементов. Пусть М-мн-во особой природы. На указанном мн-ве введем алг унарную операцию «–» и две бинарные операции «» и «».

Пусть указанные операции обладают след св-вами:

1.закон двойного отрицания:

2.законы идемпотентности:

3.законы коммутативности:

4.законы ассоциативности:

5.законы дистрибутивности:

6.законы поглощения:

7.законы де Моргана:

Мн-во М с введенными операциями, кот облад св-вами 1-7 называют булевой алгеброй.

Будем рассматривать понятие булевой алгебры в широком и узком смысле. В узком смысле понятие ф-ции Буля связано с понятием булевой алгебры.

Булевой ф-цией в узком смысле называют формулу алгебры высказываний, не содержащую операции эквиваленции и импликации.

N-местной булевой ф-цией в широком смысле будем называть n-местнуюф-цию, область определения которой , а мн-во значений также {0;1}.

Всего булевых ф-ций от n переменных .

Согласно комбинаторному правилу умножения булевых функций от 2-х переменных-16=2⁴.

x

y

1`

6. Пусть -мн-во всевозможных унарных и бинарных связок-их 20. Обозначим через мн-во основных связок. . Обозначим через Ф()-мн-во формул, содержащих связки из . Ф )-мн-во формул, содержащих связки из .

Мн-во называют ПСС, если любая формула из Ф ) равносильна некоторой формуле из Ф(): .

Св-ва ПСС: 1)Само мн-во СС явл-ся ПСС, поскольку любая формула из Ф ) равносильна сама с собой.

2)Пусть -ПСС, , то -ПСС. Т.к. -ПСС-любая формула из Ф ) равносильна некоторой формуле из , а значит и формуле из , а значит -ПСС.

3)Пусть () , -ПСС и всякая формула из равносильна некоторой формуле из ,тогда -ПСС. Т.к. -ПСС, то , но любая формула из , а значит и g равносильна некоторой формуле h из , то используя транзитивность отношения равносильности получаем: -ПСС.

Теорема о связке отрицания. Мн-во М, содержащее лишь связку отрицание не явл-ся ПСС. Док-во: докажем методом от противного. Предположим, что М-ПСС. Рассмотрим произвольную формулу .Поэтому никакая тавтология из и никакое противоречие из не может быть равносильно ф-ции из Ф(М), след-но,М-не явл-ся ПСС (противоречие).

7. Мн-во называют ПСС, если любая формула из Ф ) равносильна некоторой формуле из Ф(): .

Теорема о связке отрицания. Мн-во М, содержащее лишь связку отрицание не явл-ся ПСС. Док-во: докажем методом от противного. Предположим, что М-ПСС. Рассмотрим произвольную формулу .Поэтому никакая тавтология из и никакое противоречие из не может быть равносильно ф-ции из Ф(М), след-но,М-не явл-ся ПСС (противоречие).

Теорема. Следующие мн-ва явл-ся ПСС: 1)М₁={ } 2)M₂={ } 3)M₃={ } 4)M₄={ } 5)M₅={ }

Док-во: 1)для док-ва того, что М₁-ПСС достаточно выразить эквиваленцию через связки М₁: M₁-ПСС. 2)Используя 3-е св-во ПСС и то, что M₁-ПСС для док-ва утв2 достаточно выразить импликацию через связки из М₂: М₂-ПСС. 3)т.к. М₂-ПСС, то согласно св-ву3 ПСС выразим дизъюнкцию через связки из М₃: М₃-ПСС. 4)выразим конъюнкцию 5)т.к. М₄-ПСС, то выразим связки из М₅: М₅-ПСС.

8. Теорема. Мн-ва {\},{ }-ПСС. Док-во: Для док-ва воспользуемся св-вом3 ПСС и тем, что { } и { } также явл-ся ПСС. 1){\}-ПСС-? Для док-ва выразим через \: 2)){ }-ПСС-? след из св-во3 ПСС и M₄={ }-ПСС: .

Теорема. (о исключительности одноэлементных связок) Мн-во,содержащее {*} -ПСС . Других одноэлементных ПСС не сущ-ет.

9. Алгоритм построения СДНФ на основе построения таблицы истинности.

1.Построим таблицу истинности формулы.

2.Выделим те логические возможности формулы, на которых она принимает значение истина

3.Для выделенных логических возможностей составим истинные ЭК

4.Беря дизъюнкцию ЭК строим СДНФ.

Заметим, что формула и ее СДНФ, построенная по указанному алгоритму будут равносильными, т.к. на выделенных логических возможностях, одна из ЭК, входящих в СДНФ будет истинной, а значит и СДНФ также истинной, как и сама формула. В оставшихся логических возможностях каждая ЭК, входящая в СДНФ будет ложной, а значит ложной будет и СДНФ, как и сама формула.

Алгоритм построения СКНФ на основе таблицы истинности.

1.Построим таблицу истинности формулы.

2.Выделим те логические возможности формулы, на которых она принимает значение ложь

3.Для выделенных логических возможностей составим ложные ЭД

4.Беря конъюнкцию ЭД строим СКНФ.

Заметим, что формула и ее СКНФ, построенная по указанному алгоритму будут равносильными, т.к. на выделенных логических возможностях, одна из ЭД, входящих в СКНФ будет ложной, а значит и СКНФ также ложной, как и сама формула. В оставшихся логических возможностях каждая ЭД, входящая в СКНФ будет истинной, а значит истинной будет и СКНФ, как и сама формула.

10. Булевы ф-ции широко применяются приописании работы контактных схем, логических сетей и т.д., при исследовании некоторых электрических цепей, называемых релейно-контактных схем. Под РКС понимается устройство из проводников и двухпозиционных контактов. Контакты РКС могут быть 2-х типов: замыкающие и размыкающие. Каждый контакт подключен к некоторому реле. К одному реле может быть подключено несколько контактов, как замыкающих, так и размыкающих. Каждому реле ставится в соответствие своя булева переменная, которая принимает значение 1, когда реле срабатывает, и принимает значение 0 при отключении реле. На чертеже все замыкающие контакты, подключенные к реле x, обозначаются х, а все размыкающие контакты, подключенные к реле обозначаются . Каждая РКС, в которой занято n независимых реле определяет некоторую булеву ф-цию от n аргументов. Она принимает значение 1, когда данная схема проводит электрический ток. Схема последовательно соединенных контактов х и у проводит электрический ток титт, когда оба контакта х и у замкнуты, т.е. когда обе переменные принимают значение 1 и удовлетворяет условию . Схема, состоящая из 2-х параллельно соединенных контактов проводит электр ток в том и только в том случае, когда по меньшей мере один из контактов замкнут, т.е. когда хотя бы одна из булевых переменных принимает значение 1 и удовл условию . При решении задач используют анализ или синтез РКС: Анализ закл в след, для схемы составляется формула, которая на основании законов логики упрощается и для нее строится новая, более простая схема. Синтез схем заключается в построении схем с заданными электрическими св-вами. На основании заданных электр св-в строится формула алгебры высказываний, а по ней соответствующая схема.

11. ЭД от n переменных будем называть Д этих переменных или их отрицаний и обозначать: . ЭК от n переменных будем называть К этих переменных или их отрицаний и обозначать: .

КНФ формулы АВ будем называть равносильную ей формулу, представляющую собой К ЭД. ДНФ формулы АВ будем называть равносильную ей формулу, представляющую собой Д ЭК.

Теорема (о ЭД). ЭД от n переменных тождественно истинна титт, когда она содержит некоторую переменную одновременно с ее отрицанием.

Док-во: ()докажем теорему методом от противного. Пусть ЭД тождественно истинна, но не содержит никакой переменной одновременно с ее отрицанием. Тогда придадим всем переменным, входящим в запись ЭД без знака отрицания значение 0, а со знаком отрицания значение 1. В рез-те получаем Д нулей, которая ложна. Противоречие. ()Пусть ЭД содержит переменную одновременно с ее отрицанием, тогда эту ЭД можно, согласно законам ассоц и коммут представить в виде: ЭД

Теорема (о ЭК). ЭК от n переменных тождественно ложна титт, когда она содержит некоторую переменную одновременно с ее отрицанием.

Док-во: ()докажем теорему методом от противного. Пусть ЭК тождественно ложна, но не содержит никакой переменной одновременно с ее отрицанием. Тогда придадим всем переменным, входящим в запись ЭК без знака отрицания значение 1, а со знаком отрицания значение 0. В рез-те получаем К единиц, которая истинна. Противоречие. ()Пусть ЭК содержит переменную одновременно с ее отрицанием, тогда эту ЭК можно, согласно законам ассоц и коммут представить в виде: ЭК

12. Критерий тождественной истинности. Ф-ла АВ тождественно истинна титт, когда каждая ЭД, входящая в КНФ ф-лы содержит некоторую переменную одновременно с ее отрицанием.

Док-во: Пусть ф-ла АВ

Критерий тождественной ложности. Ф-ла АВ тождественно ложна титт, когда каждая ЭК, входящая в ДНФ ф-лы содержит некоторую переменную одновременно с ее отрицанием.

Док-во: Пусть ф-ла АВ

13. СДНФ будем называть ДНФ этой формулы, обладающую св-вами совершенства.

Св-ва совершенства. 1)Любая ЭК, входящая в ДНФ должна содержать все переменные, входящие в запись рассматриваемой формулы. 2)Все ЭК различны. 3)Ни одна из ЭК не содержит некоторой переменной одновременно с ее отрицанием. 4)Ни одна из ЭК не содержит никакую их переменных дважды.

СКНФ формулы будем называть КНФ этой формулы, обладающую св-вами совершенства. Св-ва совершенства для КНФ будут касаться ЭД. Их можно получить из записанных выше заменой фразы ЭК на ЭД.

14.С ложение по модулю 2 явл-ся бинарной операцией .

Св-ва операции сравнимости по модулю 2:

1) .

2) .

3)

4)

5) . .

6)

7)

8) .

15. -монотонна, если для каждых сравнимых логич возможностей выполняется. .

16. Полиномом Жегалкина от n переменных наз-ся булева ф-ция след вида:

Всего слагаемых в ПЖ от n переменных будет . Сущ-ет 2алгоритма построения ПЖ, кот основаны на след теореме.

Теорема. Любая булева ф-ция может быть представлена ПЖ и его представление единственно.

1способ получения ПЖ основанный на методе равносильных преобразований для БФ заданных в виде ДНФ:1)Найдем ДНФ формулы, учитывая, что и ; 2)Заменим Д в ДНФ используя закон де Моргана. При этом все отрицания переменных заменяем прибавлением 1; 3)Используем закон дистрибутивности К относительно , раскроем скобки в полученных выражениях, учитывая св-во4. В рез-те получим ф-цию в виде ПЖ.

2способ построения ПЖ основан на табл истинности для Д формы:1)Построим табл истинности для ф-ции; 2)Запишем ПЖ для указанной ф-ции через неопределенные коэф-ты; 3)Подставляя в полученный ПЖ все логические возможности ф-лы поочереди начиная с наименьшей и учитывая, что ф-ла и ПЖ равносильны найдем из полученных ур-й неизвестные коэф-ты.

; ; ; ; .

17. -класс линейных функций. БФ от называется линейной, если ее многочлен Жегалкина линеен, т.е имеет вид: . Построим полином Жегалкина для основных функций и выясним, какие из них принадлежат L.

Все аксиоматические теории можно разбить на 2 класса: содержательные и неформальные. В основу и тех и других положен аксиоматический метод, однако в содержательных теориях правила вывода новых утверждений из аксиом не постулируются, в формальных же теориях, правила вывода постулируются. Для построения формально-аксиоматической теории необходимо задать: язык теории, систему аксиом, правила вывода.

1)Язык ИВ. Алфавитом ИВ будем называть конечное мн-во символов-букв латинского алфавита, снабженных, быть может индексами, расширенного символами операций и скобками,т.е. . Формулой ИВ будем называть:1)всякую букву лат алфавита, возможно с индексами;2) если a и b-формулы, то ф-ми также явл-ся ;3)других формул, кроме определенных пунктами 1),2) не существует.

2)Система аксиом ИВ: А1. A2. A3.

3)Правила вывода ИВ. 1.правило подстановки заключается в том, что указанная система аксиом в том смысле, что вместо a,b,c, входящих в запись А1,А2,А3 могут быть подставлены любые формулы ИВ. 2.modus ponens указанное правило может записать в виде двуместной ф-ции след вида: .

18. Т₁-класс БФ, сохраняющих единицу. Если . Т₂-класс БФ, сохраняющих ноль. Если .

-класс самосопряженных (самодвойственных) функций. Если .

.

f			S	L	M
	+	+	+	+	+
	-	-	+	+	-
	+	+	-	-	+
	+	+	-	-	+
	+	-	-	-	-
	+	-	-	+	-
	-	-	-	-	-
	-	-	-	-	-
	-	+	-	+	-
0	-	+	+	+	+
1	+	-	+	+	+

Теорема Поста. Система БФ является полной титт, когда для каждого из 5 введенных классов с системе найдется функция, не принадлежащая какому-либо классу. Иными словами, Система БФ является полной титт, когда в любом столбце таблицы Поста указанной системы стоит хотя бы один минус.

Выводом формулы F длины n будем называть посл-ть формул F₁,F₂,..,F_n, причем последняя формула этой посл-ти явл-ся формулой F.

Формула F наз-ся доказуемой, если сущ-ет вывод, оканчивающийся этой формулой, причем каждая формула вывода явл-ся либо аксиомой, либо получена из них по правилам вывода. Доказуемые формулы будем называть теоремами и обозначать: ├F.

Поскольку в выводе любой теоремы присутствуют аксиомы, поэтому определение доказуемых ф-л можно расширить след образом: ф-ла доказуема, если в ее выводе содержатся либо аксиомы, либо теоремы, либо ф-лы получены из них по правилам вывода.

Заметим, что аксиомы ИВ-это теоремы, длина которых n=1.

Пусть Н={H₁,H₂,..,H_n}-некот мн-во произвольных формул ИВ. Формулу F ИВ будем называть выводимой из мн-ва Н и записывать: Н├F,если сущ-ет вывод, оканчивающийся этой формулой, причем каждая формула вывода явл-ся либо аксиомой, либо теоремой, либо принадлежит мн-ву Н, либо получена из них по правилам вывода. Мн-во Н-мн-во гипотез, F выводима из мн-ва гипотез.

Выводимые из мн-ва гипотез ф-лы не явл-ся теоремами, поскольку в их выводе присутствуют произвольные ф-лы ИВ.

Теорема.(Критерий доказуемости) Формула F ИВ доказуема титт, когда она выводима из пустого мн-ва гипотез. Док-во: () -аксиом или теорем, либо из них по правилам вывода . () -аксиом или теорем, либо из них по правилам вывода .

19. Под проблемой разрешимости формул АВ понимают проблему отнесения формулы к определенному классу. Говорят, что проблема разрешимости алгоритмически разрешима, если существует алгоритм, позволяющий классифицировать формулы.

Теорема. Проблема разрешимости формул АВ разрешима. Для док-ва приведем алгоритм отнесения формулы к одному из 3-х классов: Алгоритм. 1)найдем КНФ формулы. Используя критерий тождественной истинности определим, явл-ся ли указанная формула тождественно истинной. Если ее КНФ . Если нет, то пункт2. 2)найдем ДНФ формулы. Используя критерий тождественной ложности определим, явл-ся ли формула тождественно ложной. Если ДНФ , если нет, то пункт3. 3)формула выполнима. Алгоритм. Основан на таблице и заключается в том, что в зависимости от вида столбца этой таблицы, отвечающего за значение истинности формулы можно сделать вывод о принадлежности ее к определенному классу, а именно, если этот столбец содержит только 1-тавтология, только 0-противоречие, во всех остальных случаях-формула выполнима-1 и 0.

Вывод формулы ├А А: 1)А1.(а=А, b=A) ├A (A A) 2)A2.(a=b=c=A) ├(A (A A)) ((A A) (A A)) 3)MP(2,3) ├(A A) (A A) 4)A1.(a=A, b=A A) ├A ((A A) A) 5)A2. (a=A, b=A A, c=A) ├(A ((A A) A)) ((A (A A)) (A A)) 6)MP(4,5) ├(A (A A)) (A A) 7)MP(1,6) ├А А.

Свойства выводимости из гипотез:

1) т.е мн-во гипотез можно расширять: Н-мн-во гипотез, W-либо ф-ла ИВ или некоторое мн-во формул, H,W=H W.

2) ,где H,W-мн-во формул, С-некотор ф-ла ИВ, А-некотор ф-ла ИВ. Данное свойство означает, что в выводе ф-лы А можно заменять некоторое мн-во формул одной из которых она выводится. Справедливость данного св-ва следует из определения доказуемых ф-л и выводимых из гипотез.

3) . . Тогда заменим в (1) ф-лу С ее выводом из Н, тогда в рез-те получим А₁,А₂,…,С₁,С₂,…С_m,…А_n=А(2), где (2)-вывод А из Н.

4) . Т.к. из

5) . сущ-ет вывод, оканчивающийся этой формулой В₁,В₂,…,В_n=C . Рассмотрим по св-ву 3 и добавим в него ф-лу С. В₁,В₂,…,В_n=C ,С, но по правилу МР получим, что из .

20. Теорема дедукции. H,A├B H├A B. Док-во: H,A├B B₁,B₂,…,B_n=B причем в этом выводе B_i либо аксиомы, либо теоремы, либо принадлежат мн-ву Н, либо получены из них по правилам вывода. Докажем ММИ по длине n вывода справедливость указанной теоремы:1)проверим справедливость при n=1. В этом случае формула может быть ; а) H,A├B₁; б)А1.(а=В₁, b=А)├В₁ (А В₁); в) H,A├А B₁ покажем, что если В₁ совпадает с А, то ,├А А . Т.о., при n=1 теорема вып-ся. 2)предположим, что условие теоремы вып-ся для всех n<k и покажем 3) вып-ся и для n=k. При n=k формула В_k может быть: а)B_n-аксиома или теорема; в)В_k=A; г) В_k по правилу вывода МР В_k получено из С и С₁, кот имеют след вид:С=В_j (j<k),C=B_j .Покажем, что из . Пусть -аксиома. 1)├ ; 2) ├ 3)МР(1,2): ├А . Пусть . 1) ; 2) ├ ; 3) МР(1,2): . Пусть В_k=A т.к.├А А . г)Пусть теперь формула получена из предыдущих по правилу вывода. Поскольку формулы С и С₁ стоят перед , а значит длина их вывода меньше k и для них справедлива данная теорема, а значит выводимой будет формула H├A Си H├A С₁ и поэтому будем использовать их при выводе формул : 1) ; 2) ; 3)А2..(а=А, b= )├() ) ; 4)MP(1,4)

21. Правило исключения промежуточной посылки (ПИПП): А (В С), В├А С. Рассмотрим мн-во гипотез след вида: Н={ А (В С),В,А}покажем, что ,т.е. А (В С),В,А├С=D, А (В С),В├А С. 1) А (В С) ; 2)В ; 3)А ; 4)МР(3,1) Н├В С;5)МР(2,4) ПИПП спр-во. Сформулируем ПИПП для вывода теорем ИВ: -ПИПП-ПВ.

Правило силлогизма (ПС): А В, В С├А С. Рассмотрим 3формулы:Н={А В, В С,А}, если А В, В С, А├С А В, В С├А С. 1) А В ; 2) В С ; 3)А ; 4)МР(3,1) ; 5)МР(4,2) ПС спр-во. -ПС.

Правило перестановки посылок (ППП): А (В С)├В (А С).Н={ А (В С),В,А}. А (В С),В,А А (В С),В├А А (В С)├В (А С).Строим вывод С: 1) А (В С) ; 2)В ; 3)А ;4)МР(3,1) С; 5)МР(2,4) ППП спр-во. -ППП.

22. Закон противоречивой посылки. ├ ( В). Н={ ,А}.Покажем, что из : 1) ;2)А ;3)А1. (); 4)МР(1,3)├ ; 5)А3.)├ (() В); 6)МР(4,5)Н├() В; 7)А1.├А (); 8)МР(2,7) Н├(); 9)МР(8,6) . Т.о. ,А├В В ├ ( В).

Закон контрапозиции. а)├ () ( В). б)├(А В) ().Рассмотрим а) Н={ ,А}.Треб показать, что . Строим вывод. 1) ; 2)А ; 3)А3.├ () (( В); 4)МР(1,3) ; 5)А1.├ ; 6)МР(2,5) ; 7)МР(6,4) .Мы получили ,А├В ( В) ├ () ( В). А, ├В () В )├А (() В).

Обобщенное правило противоречивой посылки (ОППП). ├( В) (( В) В).Н={( В),( В)}.Треб показать, что . Строим вывод. 1) В ; 2) В ; 3)ЗК б)├(А В) (); 4)МР(1,3)Н├ ; 5)А3.├ () (( В); 6)МР(4,5)Н├( В;7)ЗК () ((; 8)МР(2,7) Н├ . В, В├В ( В)├( В) ├( В) (( В) В).