Студопедия Главная Случайная страница Задать вопрос

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

Формульное задание функций алгебры логики





 

Дадим индуктивное определение формулы над множеством. Это определение несколько сложное по форме, но будет полезно в дальнейшем. С индуктивным определением мы встречались в математическом анализе при определении n-го дифференциала dnf(x) : было введено понятие первого дифференциала df(x), а затем n-й дифференциал определялся как первый дифференциал от d(n–1)f(x).

Определение 1. Пусть МÌP2, тогда:

1) каждая функция f(x1, ..., xnM называется формулой над M;

2) пусть g(x1, ..., xmM , G1, ..., Gm – либо переменные, либо формулы над M. Тогда выражение g(G1...Gn) – формула над M .

Формулы будем обозначать заглавными буквами: N[f1, ..., fs], имея в виду функции, участвовавшие в построении формулы, или N(х1, ..., xk) имея в виду переменные, вошедшие в формулу. Gi – формулы, участвовавшие в построении g(G1, ..., Gn), называются подформулами.

Пример 1. Пусть N={(x1&x2),(x1Úx2),(`x )}, тогда ((х1&х2х3) – формула над N.

Сопоставим каждой формуле N(x1, ..., xn) функцию f(x1, ..., xnP2. Сопоставление будем производить в соответствии с индуктивным определением формулы.

1) Пусть N(x1, ..., xn)=f(x1, ..., xn), тогда формуле N(x1, ..., xn) сопоставим функцию f(x1, ..., xn).

2) Пусть N(x1, ..., xn)=g(G1, ..., Gm), где каждое Gi – либо формула над M, либо переменная, тогда по индуктивному предположению каждому Gi сопоставлена либо функция fiÎP2 , либо переменная хi , которую можно считать тождественной функцией. Таким образом, каждой формуле Gi сопоставлена функция fi( ), причем:{ }Í{x1, ..., xn}, т.к. в формуле N(x1, ..., xn) перечислены все переменные, участвовавшие в построении формулы. Можно считать, что все функции fi зависят от переменных (x1, ..., xn), причем какие-то переменные могут быть фиктивными. Тогда N(x1, ..., xn) = g(G1, ..., Gm) = g( f1(x1, ..., xn), ..., fm(x1,..,xn)). Сопоставим этой формуле функцию h(x1, ..., xn) следующим образом: пусть (a1, ..., an) – произвольный набор переменных (x1, ..., xn). Вычислим значение каждой функции fi на этом наборе, пусть f(a1, ..., an)=bi, затем найдем значение функции g(x1, ..., xm) на наборе (b1, ..., bm) и положим h(a1, ..., an) = g(b1, ..., bm) = g(f1(a1, ..., an), ..., fm(a1, ..., an)). Так как каждое fi(x1, ..., xn) есть функция, то на любом наборе (a1, ..., an) она определяется однозначно, g(x1, ..., xm) – тоже функция, следовательно, на наборе (b1, ..., bn) она определяется однозначно, где h(x1, ..., xn) есть функция, определенная на любом наборе (a1, ..., an).

Множество всех формул над M обозначим через <M>.

Определение 2. Две формулы N и D из <M> называются равными N=D или эквивалентными N~D , если функции, реализуемые ими, равны.

Пример 2.Доказать эквивалентность формул:

( &(х2Åx3))~( ) .

x1 x2 x3 x2Åx3 & x2 x3 x3 x2 & Úx1

 

Упрощение записи формул:

1) внешние скобки можно отпускать;

2) приоритет применения связок возрастает в следующем порядке: ~, , Ú,&;

3) связка – над одной переменной сильнее всех связок;

4) если связка – стоит над формулой, то сначала выполняется формула, затем отрицание;

5) если нет скобок, то операции ~ и выполняются в последнюю очередь.






Дата добавления: 2014-11-12; просмотров: 345. Нарушение авторских прав

Studopedia.info - Студопедия - 2014-2017 год . (0.005 сек.) русская версия | украинская версия