Основные положения дискретной математики (стр. 8 из 11)

х=И или

И

если х=И

И, И,

если

и z = И

II.

и

х =И или y =И и х=И или z=И

если х=И

И

если y=И и z=И

=И

(И – «истина», т. е. присваивается истинное значение)

В процессе доказательства равносильностей может возникнуть необходимость перехода от одной равносильности к другой. Осуществляется переход можно заменой одних логических связок на другие.

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

Пусть

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

1.

2.

3.

4.

5.

6. С А

С В

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

Пусть

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

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

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

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

Тавтологии

Дана формула А х₁ х₂ х₃.

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

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

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

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

Например

А
И	Л	Л
Л	И	Л

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

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

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

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

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

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

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

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

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

, где .

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

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

f₁(x₁,x₂,…x_k1)

f₂(x₁,x₂,…x_k2)

…………….

F_e(x₁,x₂,…x_ke)

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

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

- замена переменной. f(x₁, x₂, x_j,…,x_n) f^*=f(x₁, x₂, x_j-1,y, x_j+1,…,x_n)

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

f^*=f_i(x₁, x₂, x_j-1, f_e(x₁,x₂,…x_ke) x_j+1,…,x_ki).

Пример: система функций

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

Система функций

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

Задание №7

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

.

Для наглядности эту систему можно записать следующим образом:

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

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

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

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

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

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

Предикатом Р(х₁…х_n), называется функция P:Mⁿ

B, где М- призвольное множество, а В – двоичное множество

.

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

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

М, называются предметными переменными.

Если предикат зависит от n аргументов, то это будет n-местный предикат.

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

Рассмотрим примеры предикатов:

1. Р⁰: 2²+3²

5² – высказывание

Р¹:х²+3²

5² – одноместный предикат

Р²:х²+y²

5² – двухместный предикат

Иногда используют более простую запись: x>y – это двухместный предикат, предметной областью которого могут служить любые множества действительных чисел. Высказывание 6>6 – истинно, а 7>7 – ложно. Различные подстановки чисел вместо одной предметной переменной дают различные n – местные предикаты: x>5, x>0, 7>y и т. д.

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

6.1 Операции над предикатами

Над предикатами можно производить те же операции, что и над высказываниями:

.

Примеры:

Р¹(х): х делится на 2