Студопедия

КАТЕГОРИИ:

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



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

Читайте также:
  1. I. Решение логических задач средствами алгебры логики
  2. L – класс линейных функций.
  3. Алгоритм минимизации функций в классе нормальных форм
  4. Анатомо-морфологическая база высших психических функций
  5. Арифметические операции над непрерывными функциями. Композиция непрерывных функций
  6. Базовым принципом концепции МСС является отделение друг от друга функций переноса и коммутации, функций управления вызовом и функций управления услугами.
  7. В ЧЕМ ЗАКЛЮЧАЕТСЯ ПРОИЗВОДСТВЕННОЕ ЗАДАНИЕ
  8. Ввод формул и функций для табличных расчетов
  9. Взаимосвязь законов логики и их роль в судебной практике
  10. Взаимосвязь сущности денег и их функций.

 

Дадим индуктивное определение формулы над множеством. Это определение несколько сложное по форме, но будет полезно в дальнейшем. С индуктивным определением мы встречались в математическом анализе при определении 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-13; просмотров: 34; Нарушение авторских прав


<== предыдущая лекция | следующая лекция ==>
Элементарные функции алгебры логики | Некоторые свойства элементарных функций
lektsii.com - Лекции.Ком - 2014-2018 год. (0.008 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты