Функциональная полнота систем

Функционально полной называется такая система функций , через функции которой можно выразить любую логическую функцию.

Например, . Эта система функционально полна, так как любая функция имеет булеву формулу.

Теорема.

Произвольная система  будет функционально полной, если она сводится к функционально полной системе .

Это означает, что через функции системы  можно выразить все функции системы .

Лемма 1.

Если функция  – немонотонна, то подстановкой n-1 константы из нее можно получить отрицание.

Лемма 2.

Если функция  – нелинейна, то подстановкой n-2 констант из нее можно получить дизъюнкцию и конъюнкцию.

Функционально полной в слабом смысле называется такая система функций , которая становится функционально полной, если к ней добавить константы 0 и 1.

Например,  – функционально полна в слабом смысле. Эта система функций алгебры Жегалкина. Для того, чтоб с ее помощью можно было записать все полиномы Жегалкина, необходимо добавить константу 1. Это означает, что  – функционально полна (в сильном смысле).

Теорема 1 о функциональной полноте.

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

Лемма 3.

Если функция  – несамодвойственна, то подстановкой отрицания из нее можно получить константы 0 и 1.

Теорема 2 о функциональной полноте (теорема Поста).

Для того чтобы система функций  была функционально полна (в сильном смысле), необходимо и достаточно, чтобы она содержала

хотя бы одну немонотонную,

хотя бы одну нелинейную,

хотя бы одну несамодвойственную,

хотя бы одну не сохраняющую 0,

хотя бы одну не сохраняющую 1 функцию.

УПРАЖНЕНИЯ

1. Проверить монотонность функции, используя определение.

1) ;

2) ;

3) ;

4) ;

5) .

2. Проверить монотонность функции, используя теорему о булевой формуле монотонной функции.

1) ;

2) ;

3) ;

4) ;

5) .

3. С помощью немонотонной функции и подстановки констант получить отрицание, используя лемму 1.

1) ;  3) ;

2) ;  4) .

4. С помощью нелинейной функции и отрицания подстановкой констант получить дизъюнкцию или конъюнкцию, используя лемму 1

1) ;

2) ;

3) .

5. Проверить функциональную полноту системы логических функций. Построить таблицу Поста, сделать вывод.

1) ;   3) ;   5) ;

         2) ; 4) ;  6) .

6. Привести выражение к формуле, выраженной через функционально полную систему , , , :

1)

2)

3)

4)

7. Система состоит из одной логической функции, заданной своим вектор-столбцом. Построить таблицу Поста и сделать вывод о функциональной полноте данной системы.

1) ;   5)

2) ;    6)

3) ;    7) .

4) ;      

ГЛАВА 5. ЛОГИКА ВЫСКАЗЫВАНИЙ

И ЛОГИКА ПРЕДИКАТОВ

Логика высказываний

Высказывание – это утверждение или повествовательное предложение, которое может быть либо истинным, либо ложным.

Значением истинного высказывания является «И» – истина, ложного – «ложь».

Повелительные («Войдите, пожалуйста»), вопросительные («Который час?») и бессмысленные предложения («Сумма пяти и восемнадцати»), в которых ничего не утверждается, не являются высказываниями.

Предметом логики является анализ различных логических связей и методы построения на их основе правильных логических рассуждений.

Способы построения новых высказываний из заданных с помощью логических связок и способы установления истинности высказываний, построенных таким образом, изучаются в логике высказываний.

Основные логические связки - это связки: и, или, не, если … то…, которые в логике высказываний имеют специальные названия и обозначения. Иногда к ним добавляют еще две связки либо …, либо …(или …, или …); если, и только если (тогда и только тогда).

Для одной и той же связки в разных источниках используются разные названия и обозначения, которые приведены в таблице 1.

Таблица 1

Связка	Название	Обозначение	Высказывание, полученное с помощью связки	Математическая запись
1. и	конъюнкция (или логическое умножение)	&, Ù, ×	А и В	А & В, А Ù В, А × В, АВ
2. или	дизъюнкция	Ú, +	А или В	А Ú В, А + В
3. не	отрицание, инверсия	Ø, ¾	не А	, ØА
4. если …, то …	импликация	®, É	если А, то В (А влечетВ)
5. либо …,  либо …	исключающее «или», неравнозначность	Å, D, ¹	либо А, либо В	А Å В, А D В
6. если и только если	эквивалентность, равнозначность	º, ~, «	А, если и только еслиВ	А º В, А ~ В

В последней колонке табл. 1 записаны формулы, или выражения логики высказываний. С помощью букв А, В, С, ... обозначающих высказывания, связок и скобок можно построить разнообразные формулы.

Исследование свойств таких формул и способов установления их истинности и является основным предметом логики высказываний.

Существуют два подхода к построению логики высказываний, которые образуют два варианта этой логики: алгебру логики и исчисление высказываний.

Алгебра логики

Алгебра логики рассматривает логические формулы как алгебраические выражения, которые можно преобразовать по определенным правилам. Знаки операций обозначают логические операции (логические связки).

В формулах алгебры логики переменные – это высказывания.  Они принимают только два значения – ложь и истина, которые обозначаются либо 0 и 1, либо Л и И, либо false и true.

Каждая формула задает логическую функцию: функцию от логических переменных, которая сама может принимать только два логических значения.

Таблица функций  одной переменной:

	Константа 0:	Тождество:	Отрицание:	Константа 1:
0	0	0	1	1
1	0	1	0	1

Таблица функций двух переменных , соответствующих основным логическим связкам:

		Дизъюнкция	Конъюнкция	Импликация	Эквивалентность (равнозначность)	Неравнозначность (сложение по модулю 2)	Штрих Шеффера (НЕ – И)	Стрелка Пирса (НЕ – ИЛИ)
0	0	0	0	1	1	0	1	1
0	1	1	0	1	0	1	1	0
1	0	1	0	0	0	1	1	0
1	1	1	1	1	1	0	0	0

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

Интерпретацией формулы логики высказываний называется набор значений высказываний, входящих в нее.

Формула F называется тождественно истинной или тавтологией, если она принимает значение «истина» независимо от значений входящих в нее высказывательных переменных.Формула F называется выполнимой, если при некоторых значениях ее высказывательных переменных она принимает значение «истина». Такой набор значений высказывательных переменных называется моделью формулы F.

Исчисление высказываний

Пусть интерпретация  определена на всех высказывательных переменных, встречающихся в формулах множества . Говорят, что  выполняет  или  модель ,  если каждая формула  из  принимает значение «истина», при интерпретации . Говорят, что  выполнимо, если  имеет модель. Если  не выполнимо, то пишут ÷=.

Пусть  – множество формул логики высказываний, А – произвольная формула. Говорят, что множество  логически влечет формулу А, если любая модель  являются моделью для А и обозначается ÷= А.

Утверждение того, что некоторое высказывание (заключение) следует из других высказываний (посылок), называется аргументом. Аргумент часто представляют в виде:

... гипотезы

 заключение

    Аргумент называется правильным, если из множества гипотез логически следует заключение аргумента.

Второе правило исчисления высказываний: Modus Ponens.

Правило Modus Ponens: , т.е.

«Если , то ; но  истинно, следовательно, истинно ».

 

УПРАЖНЕНИЯ

1. Приведите примеры истинных и ложных высказываний из биологии, географии, физики, истории, математики, литературы.

2. Из данных предложений выберите те, которые являются высказываниями, обоснуйте выбор.

1) Коля спросил: «Который час»?

2) Как пройти в библиотеку?

3) Картины Пикассо слишком абстрактны.

4) Решение задачи – информационный процесс.

5) Число 2 является делителем числа 7 в некоторой системе счисления.

3. Выберите истинные из данных высказываний:

1) Город Лондон – столица Великобритании.

2) Число 3 является делителем числа 9.

3) Город Стокгольм – столица Германии.

4) Клавиатура – средство ввода информации.

5) Число 8 кратно 3.

6) Принтер – средство вывода информации.

7) Меню в программе – список возможных вариантов.

8) Для всех х из области определения  верно, что х+2 > 0.

9) II+VI > VIII.

4. В приведенных предложениях вместо многоточия поставьте подходящие по смыслу слова: «необходимо», «достаточно», «необходимо и достаточно». Обозначив часть предложения до многоточия за А, а часть после многоточия за В, записать формализованное высказывание, используя подходящую логическую связку.

1) Для того, чтобы число делилось на 4, ... чтобы оно было четным.

2) Что бы число делилось на 3, ... что оно делилось на 9.

3) Для того чтобы число делилось на 10, ... чтобы оно оканчивалось на 0.

4) Чтобы произведение двух чисел равнялось 0, ... чтобы каждое из них равнялось 0.

5) Чтобы произведение двух чисел равнялось 0, ... чтобы хоть одно из них равнялось 0.

6) Чтобы умножить сумму нескольких чисел на какое-либо число, ... каждое слагаемое умножить на это число и полученные произведения сложить.

7) Чтобы произведение нескольких чисел разделить на какое-либо число, ... разделить на это число только один сомножитель, и полученное частное умножить на остальные сомножители.

8) Для того, чтобы сумма двух чисел была четной, ... чтоб каждое из них было четным числом.

9) Для того, чтобы число делилось на 10, ... чтобы оно делилось на 5.

10) Для того, чтобы число делилось на 6, ... чтобы оно делилось на 2 и на 3.

11) Для того, чтобы число делилось на 12, ... чтобы оно делилось на 2 и на 3.

12) Чтобы четырехугольник был квадратом, ... чтоб все его стороны были равны.

5. Формализовать сложное высказывание: разбить его на простые высказывания и связать их подходящими логическими связками.

1) Число 376 четное и трехзначное.

2) Зимой дети катаются на коньках или лыжах.

3) Новый год мы встретим на даче или на Красной площади.

4) Неверно, что Солнце движется вокруг Земли.

5) Если сейчас не солнечно, то пасмурно.

6) Земля имеет форму шара, который из космоса кажется голубым.

7) На уроке математики старшеклассники отвечали на вопросы учителя, а также писали самостоятельную работу.

8) Если вчера было воскресенье, то Дима не был в школе и весь день гулял.

9) Если сумма цифр натурального числа делится на 3, то и число делится на 3.

10) Число делится на 15 тогда и только тогда, когда оно делится на 3 и на 5.

6. Постройте отрицание следующих выражений.

1) Сегодня в театре идет опера «Евгений Онегин».

2) Число 2 есть простое число.

3) Число 3 – составное.

4) Каждый охотник желает знать, где сидит фазан.

5) Натуральные числа, оканчивающиеся на 0, являются простыми.

6) Неверно, что число 3 не является делителем числа 198.

7) Коля решил все задачи контрольной работы.

8) Неверно, что любое число, оканчивающееся на 4 делится на 4.

9) Во всякой школе некоторые ученики интересуются спортом.

10) Некоторые млекопитающие не живут на суше.

7. Являются ли отрицанием друг друга высказывания А и В.

1) А – «он мой друг»; В – «он мой враг».

2) А – «дом большой»; В – «дом небольшой».

3) А – « х > 2 »; В – « х < 2 ».

4) А – «две карты красные»; В – «две карты черные».

5) А – «две карты разные»; В – «две карты одинаковые».

6) А – «студент - девушка»; В – «студент - юноша».

7) А – «число четное»; В – «число нечетное».

8) А – «число положительное»; В – «число отрицательное».

9) А – «студент курит и живет в общежитии»; В – «студент не курит и не живет в общежитии».

10) А – « х ≤ 3»; В – « х > 3 ».

11) А – « »; В – « ».

12) А – « »; В – « ».

13) А – « »; В – « ».

8. А – «Число 5 простое»; В – «Луна – спутник Венеры». Выразить обычным языком составные высказывания. Определите их истинность.

1) ;	4) ;	7) ;	10) ;
2) ;	5) ;	8) ;	11) ;
3) ;	6) ;	9) ;	12) .

9. Какие из составных высказываний истинные.

1) У розы шипы и трава зеленая.

2) У розы шипы или трава красная.

3) Если у розы шипы, то трава красная.

4) Если трава красная, то у розы шипы.

5) Если трава синяя, то Земли спутник Луны.

6) Земля спутник Луны тогда и только тогда, когда трава красная.

7) Земля спутник Луны или Луна спутник Земли.

8) Неверно, что Земля спутник Луны и у розы шипы.

10. Для высказываний А и В определить истинность с семантический смысл и истинность составного высказывания:

1) A – Иван водит машину (истинно); В – мы без проблем доберемся до дома.

; .

2) A – Лариса любит гонять на мотоцикле; В – быстро ездить опасно; С – жизнь Ларисы в опасности.

; .

11. Являются ли следующие формулы выполнимыми Тождественно истинными Перечислить множество всех моделей формулы F.

1) ;             3) ; 5) ;

2) ; 4) ; 6) .

12. Выполнимо ли множество формул:

1) ;                       3) ;   

2) ;  4) .

13. Верно ли, что

1) ÷= ;                          3)  ÷= ;   

2)  ÷= ;                       4)  ÷= .

14. Выяснить, являются ли следующие рассуждения логически правильными. Для этого представить каждое предложение в виде формулы и проверить, является ли заключение логическим следствием посылок.

1) Если Джон – коммунист, то Джон – атеист. Джон – атеист. Следовательно, Джон – коммунист.

2) Если этот курс хорош, то он полезен. Или экзаменатор снисходителен, или этот курс бесполезен. Но экзаменатор не снисходителен. Следовательно, этот курс плох.

3) Для того, чтобы перейти на следующий курс, достаточно сдать этот предмет по крайней мере на 3. Я сдам этот предмет лишь в том случае, если разберусь с доказательством теоремы. Но я не в состоянии разобрать доказательство этой теоремы. Следовательно, я перейду на следующий курс.

15. Определить, какие из следующих аргументов являются правильными:

1)              2)             3)            4)

                                    

                                        

                                                          

Логика предикатов

С помощью формул логики высказываний можно описать структуру сложных высказываний. Для описания внутренней логической структуры простых высказываний (т.е. высказываний, не содержащих связок) используются другие средства, которые вместе с логикой высказываний образуют логику предикатов.

Чтобы яснее представить о какой логической структуре идет речь, рассмотрим пять высказываний:

1. 15 – нечетное число.

2. 8 – нечетное число.

3. 6 5.

4. В Ярославле жителей больше, чем в Вязьме.

5. В Москве жителей больше, чем в любом другом городе России.

Все эти высказывания – простые и, следовательно, в логике высказываний изображаются одной буквой. Все, что о них можно сказать в этой логике, – это то, что высказывание (2) ложно, а остальные – истинны.

В то же время ясно, что между высказываниями (1) и (2) или между (4) и (5) сходства гораздо больше, чем между (1) и (5).

В высказываниях (1) и (2) речь идет о числах, которым приписывается одно и то же свойство – нечетность. В высказывании (3) утверждается наличие отношения неравенства между числами. В высказываниях (4) и (5) говорится о городах, относительно которых утверждается наличие некоторого отношения между ними – «иметь больше жителей».

Числа и города – это объекты. Множество объектов (целых чисел, городов России и т.д.), о которых делаются утверждения, называется предметной областью, а сами утверждения об отношениях между  объектами называются n-местными предикатами.

С математической точки зрения:

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

Нечетность – это одноместный предикат. Если его обозначить через , тогда высказывания (1) и (2) запишутся как  и , т.е. как один и тот же предикат нечетности с разными значениями (15 и 8) переменной , взятыми из одной и той же предметной области целых чисел.

«Иметь больше жителей» – это двуместный предикат . Высказывание (4) можно записать как .

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

Таким образом, формулы вида  и  - это переменные высказывания, которые становятся истинными или ложными при подстановке вместо  и  предметных констант – конкретных объектов из предметных областей.

Кроме того, из предикатов можно получать конкретные высказывания, не содержащие предметных констант, а утверждающих нечто обо всей предметной области.

В естественном языке это делается с помощью оборотов «для всех  (т.е. для всех объектов) справедливо, что…» и «существует такой , что…».

В языке формул логики предикатов этим оборотам соответствуют специальные знаки – кванторы: квантор общности  и квантор существования .

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

Например, формула  означает «для всех целых чисел справедливо то, что они нечетны»  или, короче, «все целые числа – нечетны». Это – конкретное высказывание, которое ложно. Формула  означает истинное высказывание «существуют нечетные целые числа».

Если квантор навешивается на формулу с несколькими предметными переменными, то он уменьшает число свободных (несвязанных) переменных в этой формуле. Например, формула  обозначает высказывание «в городе  больше жителей, чем в любом городе « и содержит одну свободную переменную . Это высказывание ложно для любого , потому что «любой город» подразумевает в том числе и , но ни в каком городе не может быть больше жителей, чем в нем самом. «Шансы на истинность» имеет уточненное высказывание: «в городе  больше жителей, чем в любом другом городе , не совпадающем с »:

,

в которой оба вхождения переменной  связаны квантором (с помощью скобок). Подстановка «Москва» вместо  дает формулу, выражающую истинное высказывание (5).

Как и в логике высказываний, в логике предикатов имеются эквивалентные соотношения, позволяющие преобразовывать предикатные формулы. Например,

- один квантор можно выразить через другой:

, ,

- формулу, не содержащую переменную , можно вынести за пределы действия квантора, связывающего :

; .

Однако, в целом, логику предикатов не удается представить в виде алгебры, столь же эффективной как алгебра логики (т.к. вычисление истинности предикатов, содержащих кванторы, в общем случае заключается в подстановке всех возможных значений предметных переменных, которых может быть бесконечное множество).

Поэтому логика предикатов организуется в виде исчисления предикатов, которое содержит аксиомы и правила вывода исчисления высказываний, а также дополнительные предикатные аксиомы и правила вывода.

В качестве аксиом обычно принимаются две формулы:

,                                 (1)

              ,                                 (2)

где  – любая предикатная формула, содержащая свободную переменную , а в качестве правил вывода – правила, вводящие кванторы:

   ,                    (3) 

                  ,                         (4)

в этих правилах требуется, чтобы формула  содержала свободную переменную , а  ее не содержала.

Пример.

Рассмотрим известнейший силлогизм, на протяжении двух тысячелетий переходящий из одних ученых трудов в другие:

Все люди смертны.

Сократ – человек.                         .