Основные положения дискретной математики

Рефераты / Математика / Основные положения дискретной математики

Правила перехода от одних равносильностей к другим

Пусть , а С - произвольная формула

6. С АС В

Правила равносильных преобразований

Пусть , а С - произвольная формула. Пусть х - формула, которая входит в С. тогда Са - формула, которая получается заменой в формуле С формулы х на а.Сb - получается из С заменой x на b, тогда Са=Сb.

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

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

Пусть f и g - функции алгебры логики, x1,…,xn - совокупность аргументов, входящих хотя бы в одну из этих функций, говорят, что f и g- равносильны, если при всех значениях x1,…,xn значения f и g - совпадают.

Тавтологии

Дана формула А х1 х2 х3.

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

Тавтология – это утверждение, которое всегда истинно, иначе ее определяют как закон.

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

Противоречие – это утверждение, которое всегда ложно. Таблица истинности для противоречия всегда принимает значение «Ложь».

Например

А
И	Л	Л
Л	И	Л

Формула А называется выполнимой, если находится такой набор переменных, что она принимает значение «Истина».

Формула А называется опровержимой, если находится такой набор переменных, что она принимает значение «Ложь».

Что касается высказываний, то здесь применяется термин высказывание логически истинно, такое высказывание можно получить путем его подстановки в тавтологию (например: предложение «Если идет дождь или идет снег, и не идет дождь, то идет снег» получим путем подстановки в тавтологию и высказывание логически ложно, если его подставляют в противоречие.

Основные тавтологии

Доказательство утверждений

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

5. БУЛЕВЫ ФУНКЦИИ

5.1 Полнота системы булевых функций

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

Эти функции нам встречались в теме «Математическая логика» при составлении 16-ти функций для двух переменных.

Полная система булевых функций обозначается Е имеет следующий вид:

f1(x1,x2,…xk1)

f2(x1,x2,…xk2)

…………….

Fe(x1,x2,…xke)

Система функций (Е), называется полной, если любая ее булева функция может быть выражена с помощью f1, f2, … fe через суперпозицию.

Суперпозиция – это функция f*, которая получена из функции f с помощью следующих преобразований:

Ø замена переменной. f(x1, x2, xj,…,xn) f*=f(x1, x2, xj-1,y, xj+1,…,xn)

Ø подстановка вместо хj некоторой функции из системы (1).

f*=fi(x1, x2, xj-1, fe(x1,x2,…xke) xj+1,…,xki).

Пример: система функций (Е1) всегда полна, т. к. каждая функция этой системы может быть представлена в виде СДНФ, следовательно СДНФ является суперпозицией, через которую может быть выражена любая из функций системы;

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

Задание №7

Доказать полноту системы:

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

следовательно данная система является полной.

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

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

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

Высказывание как функция на некотором фиксированном множестве допустимых ситуаций, называется предикатом на этом множестве.

Предикатом Р(х1…хn), называется функция P:MnB, где М- призвольное множество, а В – двоичное множество .

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

М называется предметной областью предиката, а элементы этого множества (х1…хn)М, называются предметными переменными.