Сведение к абсурду (Reductio ad Absurdum)

Если из того, что А не верно, следует, что В верно и не верно одновременно, то А верно

ùА →( В & ùB )

АСведение к абсурду используется в методе доказательства, известном как доказательство от противного. Оно состоит в следующем

Предполагается, что истинным является отрицание того высказывания, которое необходимо доказать. Затем необходимо прийти к противоречию. Если это удается, то исходное утверждение доказано.

Алгебра логики. Бинарные логические операции. Существенные и несущественные (фиктивные) переменные. Функционально полные системы (базисы). Булева алгебра логики. Законы булевой алгебры. Примеры других алгебр логики.

Математическая логика состоит из двух разделов: логики высказываний и логики предикатов.

Логика высказываний может быть представлена двумя подходами: алгеброй логики (высказываний) и исчислением высказываний.

Алгебра, образованная множеством B={0,1} вместе со всеми возможными операциями на нем, называется алгеброй логики.

Алгебра логики как раздел математической логики изучает строение сложных логических высказываний (логических формул) и способы установления их истинности с помощью алгебраических методов.

Формулы алгебры логики состоят из

букв — логических (двоичных) переменных

знаков операций — логические операции (логические связки)

скобок

Каждая формула задает логическую функцию — функцию от логических переменных (т.е. принимающих значение 0,1), которая так же может принимать только два значения 0 и 1. Другими словами логическая функция имеет вид f(x1,x2,…xn): Bn→B, где В множество состоящее из двух элементов В={0,1}.

Множество всех логических функций обозначается P2, множество всех логических функций n переменных — P2(n).

Число |P2(n)| различных функций n переменных равно числу различных двоичных векторов длины 2n, т.е.

Бинарные функции (функции двух переменных)

Таблица истинности

Сведение к абсурду (Reductio ad Absurdum) - student2.ru

Фиктивные переменные

Переменная xi в функции f(x1,…, xi–1, xi, xi+1, …, xn) называется несущественной (или фиктивной), если f(x1,…, xi–1, 1, xi+1, …, xn) = f(x1,…, xi–1, 0, xi+1, …, xn) при любых значениях остальных переменных.

В этом случае f(x1,…, xn) по существу зависит от n - 1 переменной, т.е. представляет собой функцию g(x1,…, xi–1, xi+1, …, xn) от n - 1 переменной.

Говорят, что функция g получена из функции f удалением фиктивной переменной, а функция f получена из функции g введением фиктивной переменной, причем эти функции по определению считаются равными

Функционально полные системы (базисы)

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

Примерыфункционально полных систем логических функций:

{o} (Функция Вебба),

{½} (штрих Шеффера);

{®, 0}, { ®, 1},

{ &, Å, 1}

и другие.

Наиболее изученным является базис {&, Ú, Ø}. Формулы, содержащие кроме переменных и скобок знаки этих функций называются булевыми.

Основные эквивалентные соотношения (законы) в булевой алгебре

ассоциативностей aÚ(bÚc)=(aÚb)Úc, aÙ(bÙc)=(aÙb)Ùc;

коммутативностей aÚb=bÚa, aÙb=bÙa;

дистрибутивностей aÙ(bÚc)=(aÙb)Ú(aÙc); aÚ(bÙc)=(aÚb)Ù(aÚc); идемпотентностей aÚa=a, aÙa=a;

двойного отрицания ØØa=a; законы нуля (лжи) aÚ0=a, aÙ0=0, aÙØa=0; законы единицы (истины) aÚ1=1, aÙ1=a, aÚØa=1. де-Моргана ØaÚØb=Ø(aÙb), ØaÙØb=Ø(aÚb);

противоречия aÙØа=0; исключенного третьего aÚØа=1

поглощения aÚaÙb=a, aÙ(aÚb)=a; склеивания aÙb Ú aÙØb =a, (aÚb)Ù(aÚØb)=a; обобщенное склеивание aÙc Ú bÙØc Ú aÙb = aÙc Ú bÙØc; a Ú ØaÙb = aÚb

Суперпозиция булевых функций и ее формула. Глубина формулы. Таблицы истинности для сложных формул. Эквивалентность формул. Тождественно истинная, тождественно ложная и выполнимая функция. Единичный и нулевой набор функции.

Суперпозицией F булевых функций f0 и f1,...,fmназывается функция F=f0(g1(x1,...,xm),...,gn(x1,...,xm)), где каждая из функций gi(x1, ...,xm) либо совпадает с одной из переменных (тождественная функция), либо – с одной из функций f1,...,fm.

Формулой называется выражение, описывающее эту суперпозицию.

Символы переменных, а также функции const_0 и const_1 считаются формулами глубины 0.

Пусть дано множество (конечное или бесконечное) исходных функцийå={f1, ..., fm}. Любая формула F =f0(g1, ..., gn), у которой giÎS, n— количество аргументов f0,, имеет глубину k=max(k1…,kn)+1, здесь k1…,kn глубины формулg1, ..., gn.

Формулы g1, ..., gn называются подформулами F. Функция f0 называется внешней или главной операцией формулы F.

Пример: Глубина формул

Определить глубину формулы F= ((А→В)&C) ÚA.

Вначале выполняется f1= А→В. Глубина которой k1=max(0,0)+1=1

Следующей будет выполняться функция f2=f1&C. Функция f2 имеет глубину k2=max(k1,0)+1=max(1,0)+1=2

Далее выполнятся функция f3=f2ÚA, глубина которой k3=max(k2,0)+1=max(2,0)+1=3

Таким образом, глубина исходной формулы равна 3.

Наши рекомендации