Дискретная математика

Раздел 1. Математическая логика

Тема 1. Логика высказываний

Логика предикатов в качестве составной и наиболее простой части содержит логику высказываний.

§1. Высказывания и операции над ними

§2. Формулы логики высказываний, интерпретация

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


Определение. Атомарными формулами логики высказываний называются буквы U,V,W,X,Y,Z с индексами и без них, а также символы истины 1 и лжи 0.


Определение. Формулами логики высказываний называются

1)     атомарные формулы;

2)     выражения вида (F)&(G), (F)Ú(G), Ø(F), (F)®(G), (F)«(G), где F и G –

формулы логики высказываний.

На первый взгляд может показаться, что определение содержит «порочный круг»; «понятие формулы логики» высказываний определяется само за себя. На самом деле, это определение относится к так называемым индуктивным определениям. Такие определения вводят сначала базовые объекты (в нашем случае – атомарные формулы) и способы порождения новых объектов из уже полученных (в нашем случае – применение операций), введенных в первом параграфе.

Приведем пример. Буквы X,Y,Z – атомарные формулы. В силу первого пункта определения эти буквы являются формулами логики высказываний, а в силу второго формулами являются выражения (X)&(Y), ((X)&(Y))®(Z). Мы видим, что если следовать строго определению, в формуле надо писать много скобок. Это неудобно для восприятия формулы. Чтобы уменьшить количество скобок условимся, во первых, атомарные формулы в скобки не заключать, во вторых, ввести приоритет (силу связывания) для связок. Будем считать, что Ø имеет наивысший приоритет, & и Ú имеют одинаковый приоритет, который выше, чем y® и «. Последние две связки имеют одинаковый приоритет. Используя эти соглашения формулу ((X)&(Y))®(Z) можно записать так: X&Y®Z. Отметим, что поскольку мы не упорядочили & и Ú по силе связывания, то выражение X&YÚZ не является формулой. Надо в этом выражении поставить скобки, определяющие порядок выполнения операций. Получатся две формулы (X&Y)ÚZ и X&(YÚZ).

В дальнейшем нам понадобится понятие подформулы. Попросту говоря, подформула формулы F – это «слитная» часть, которая сама является формулой. На строгом уровне понятие вводится следующим образом.


Определение. Подформулой атомарной формулы является она сама. Подформулами формулы ØF являются формула ØF и все ее подформулы. Подформулами формул F&G, FÚG, F®G, F«G являются они сами и все подформулы формул F и G/

Например, формула F=X&Y®XÚZ имеет шесть подформул: X,Y,Z,X&Y, XÚZ, X&Y®XÚZ.


Теперь нам надо соотнести понятие высказывания и формулы. На самом простом уровне формула – это форма для получения высказываний. Пусть, например, дана формула F=X&Y®Z. Поставим вместо X,Y и Z соответственно высказывания А1=четырехугольник ABCD является параллелограммом, А2=в четырехугольнике ABCD смежные стороны равны, А3=в четырехугольнике ABCD диагонали перпендикулярны, то получим высказывание А4= если четырехугольник ABCD является параллелограммом и его смежные стороны равны, то диагонали перпендикулярны (использованы естественные сокращения). Это высказывание получилось «по форме» F. Если вместо X,Y и Z подставить другие высказывания, то получим новое высказывание, имеющее ту же «форму».

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

Обозначим через А – множество атомарных, а через F – множество всех формул логики высказываний. Зафиксируем некоторую совокупность высказываний P, удовлетворяющим следующим условиям: если совокупность P содержит два высказывания, то она содержит их конъюнкцию, дизъюнкцию, импликацию и эквиваленцию и отрицание (каждого из высказываний). Интерпретацией в широком смысле мы будем называть функцию


j:A®P


такую, что j(1) – истинное высказывание, а j(0) – ложное. Такая функция, определенная на множестве атомарных формул, естественным образом распространяется на множество всех формул. Выше был приведен пример интерпретации в широком смысле. В этом примере совокупность P содержала высказывания А1, – А4, а интерпретация j на атомарных формулах X,Y,Z действовала так: j(X)=A1, j(Y)=A2, j(Z)=A3. Естественно расширение j на множестве всех формул будем обозначать той же буквой. Тогда j(F)=A4.

В дальнейшем, на самом деле от высказываний j(F) нам, в основном, будут нужны только их истинные значения 1 и 0. Введем поэтому более узкое понятие интерпретации.


Определение. Интерпретацией в узком смысле (или просто интерпретацией) называется функция


j:A®{0,1}


такая, что j(0)=0, j(1)=1.

Используя таблицы истинности связок, интерпретацию можно расширить на множество всех формул. Приведем пример. Пусть j(X)=1, j(Y)=0, j(Z)=1, F=XÚY®Z, G=X&Y«Y&Z. Тогда j(F)=1, j(G)=0.

В заключение параграфа рассмотрим задачу, решение которой состоит в использовании выразительных возможностей логики высказываний. Прежде, чем дать соответствующее определение условимся о следующем обозначении. Если формула F построена из атомарных формул X1,…,Xn, то F будем обозначать через F(X1,…,Xn). Более того, мы будем пользоваться последним обозначением, даже если некоторые из атомарных формул отсутствуют в записи формулы F (но всякая атомарная формула, входящая в F, содержится среди X1,…,Xn).

§3. Равносильность и законы логики высказываний

§4. Логическое следствие.

§5. Нормальные формы в логике высказываний

§6. Контактные схемы.

Задачи

Ответы, указания и решения

Тема 2. Булевы функции

Тема 3. Логика предикатов

Тема 4. Метод резолюций

Раздел 2. Теория графов

Тема 5. Раскраски

Тема 6. Ориентированные графы и сети


Fair.ru Ярмарка сайтов
Rambler's Top100 Submitter.ru - Free promoting

Дизайн: Alex © 2002
Все вопросы и предложения можно направлять по адресу cad@mail.ustu.ru