Глоссарий по логике

№ п/п

Новые понятия

Содержание

1

Бинарное отношение

Непустое  множество упорядоченных пар элементов этого множества.

2

Обратное бинарное отношение

Двухместное отношение, состоящее из пар элементов (у, х), полученных перестановкой пар элементов (х, у) данного отношения R. Обозначается: R⁻¹. Для данного отношения и обратного ему верно равенство: (R⁻¹)⁻¹ = R. Т.е. если было «x начальник y», то при обратном бинарном отношении будет так: «x подчиненный y»

3

Композиция бинарных отношений

Применение одной функции к результату другой.

4

Свойства бинарных отношений:

а) В математике бинарное отношение  на множестве  называется рефлексивным, если всякий элемент этого множества находится в отношении  с самим собой.

Формально, отношение  рефлексивно, если .

б) В математике бинарное отношение  на множестве X называется симметричным, если для каждой пары элементов множества  выполнение отношения влечёт выполнение отношения .

в) В математике бинарное отношение  на множестве  называется транзитивным, если для любых трёх элементов множества  выполнение отношений  и  влечёт выполнение отношения .

Формально, отношение  транзитивно, если .

г) Связанное отношение — это двухместное отношение R, определённое на некотором множестве, отличающееся тем, что для любых двух различных элементов х и уиз этого множества, одно из них находится в отношении R к другому (то есть выполнено одно из двух соотношений: xRy или yRx). Пример: отношение «меньше» (

5

Отношение эквивалентности

Отношение на множестве, которое содержит свойства  рефлексивности, симметричности, транзитивности

6

Противоположное бинарное отношение

Двухместное отношение, состоящее из пар элементов (у, х), полученных с отрицанием элементов (х, у) данного отношения R. Теоретически можно сказать: не R. Т.е. если было «x начальник y», то при противоположном бинарном отношении будет так: «x не начальник y»

№ п/п

Новые понятия

Содержание

1

Булевая алгебра

Непустое множество A с двумя бинарными операциями  (аналог конъюнкции),  (аналог дизъюнкции),унарной операцией  (аналог отрицания) и двумя выделенными элементами: 0 (или Ложь) и 1 (или Истина)

2

Булевый базис

Набор трех логических функций: НЕ, И, ИЛИ называют булевским или булевым базисом в честь английского математика конца XIX в. Джорджа Буля.

3

Булевая функция

Булевой функцией  f(X1, X2, …, Xn) называется произвольная n – местная функция, аргументы и значения которой принадлежат множеству {0, 1}.

4

СДНФ

Совершенная дизъюнктивная нормальная форма-дизъюнкция элементарных конъюнкций.

5

СКНФ

Совершенная конъюнктивная нормальная форма-конъюнкция элементарных дизъюнкций.

6

Элементарная конъюнкция

Конъюнкция переменных, их отрицаний, каждое из которых использовано только 1 раз.

7

Элементарная дизъюнкция

Дизъюнкция переменных, их отрицаний, каждое из которых использовано только 1 раз.

8

Классы функций

Т0 –нулевая функция, принимает нулевое значение при нулевом наборе переменных

Т1-единичная функция, принимает значение единицы при единичном наборе переменных

L-линейная функция, если функция может быть представлена в виде Полинома Жегалкина с переменными в степени не более 1

S-самодвойственная функция, при противоположных наборах переменных принимает противоположные значения

M-монотонная функция, если она меняет свое значение в таблице истинности только 1 раз, при чем этот переход должен быть от 0 к 1

9

Полином Жегалкина

Способ задания логической функции. Для того, чтобы составить ПЖ необходимо:

1.Представить в виде ДНФ;

2.С помощью двойного отрицания и закона де Моргана избавиться от дизъюнкции;

3.Все отрицания заменить по формуле:=x+1;

4.Перемножить полученные скобки;

5.Сократить с учетом: четное количество одинаковых слагаемых превращается в 0, а нечетное- значит оставляем одну переменную

10

Теорема Поста (о полноте)

Теорема Поста (признак полноты системы булевых функций). Для того чтобы система булевых функций {f1, …, fm} была полной, необходимо и достаточно, чтобы для каждого из пяти функционально замкнутых классов T0, T1, L, M, S нашлась хотя бы одна функция fi  из системы, не принадлежащая этому классу.

11

Карта Карно

Позволяет упростить запись таблицы истинности и найти сокращенную запись функции

12

Тождественно-истинная функция

Предикат, если при всех возможных значениях переменных он принимает значение 1

13

Тождественно-ложная функция

Предикат, если при всех возможных значениях переменных он принимает значение 0

№ п/п

Новые понятия

Содержание

1

Высказывание

Повествовательное предложение, которое может быть истинным или ложным

2

Предикат

Любое математическое высказывание, в котором есть, по меньшей мере, одна переменная

3

Область истинности

Является подмножеством области определения и имеет ту же предметную природу

4

Квантор существования

Предикат свойства или отношения для, по крайней мере, одного элемента области определения. Он обозначается как символ логического оператора ∃ (произносится как «существует» или «для некоторого»).

5

Квантор всеобщности

Условие, которое верно для всех обозначенных элементов, в отличие от квантора существования, где условие верно только для каких-то отдельных из указанных чисел. Формально говоря, это квантор, используемый для обозначения того, что множество целиком лежит в области истинности указанного предиката.

6

Связная переменная

Вхождение переменной в формулу, если переменная в кванторе или переменная находиться в области квантора.

7

Свободная переменная

Если вхождение переменной в формулу не связано.

8

Выполнимая формула

Булева формула, таблица истинности которой содержит хотя бы одну 1(единицу) в правом столбце.

9

Общезначимая формула

Булева формула, таблица истинности которой содержит только 1 в правом столбце.

10

Логический парадокс

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

№ п/п

Новые понятия

Содержание

1

Алгебра Логики

Совокупность логического множества и логического базиса. Логическое множество состоит из 0 и 1 и означает истину или ложь.

2

Логическая функция

Логической ( булевой) функцией (или просто функцией) n переменных y = f(x1, x2, …, xn) называется такая функция, у которой все переменные и сама функция могут принимать только два значения: 0 и 1.

3

Логическая переменная

Переменные, которые могут принимать только 2 логических значения «истина» или «ложь»

4

Конъюнкция

(логи́ческое "И",логи́ческое умноже́ние)логическая операция относительно 2х логических переменных, которые принимают значение истины только тогда, когда обе переменные истины

5

Дизъюнкция

(логи́ческое "Или",логи́ческое сложе́ние)Логическая операция относительно 2х переменных, которые принимают ложное значение только тогда, когда обе переменные ложны

6

Импликация

(логи́ческое следование)Логическая операция относительно 2х переменных, которая принимает значение ложно, когда первая переменная истина, а вторая – ложна. Первая переменная – посылка, вторая - заключение

7

Эквивалентность

(логическая равносильность, логическое равенство) Логическая операция относительно 2х переменных, которая принимает значение истины, если переменные равнозначны

8

Инверсия

(логическое отрицание) Логическая операция относительно одной переменной, которая меняет свое значение на противоположное

9

Основные законы логики

• Основные черты правильного мышления.( мышление, которое соответствует логическим нормам и законам.)

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

• Закон непротиворечия (противоречия).( логический закон, согласно которому не могут быть одновременно истинными взаимно исключающие друг друга мысли.) Закон противоречия Математическая запись где  — знак конъюнкции,  — знак отрицания.

• Закон исключенного третьего.( закон традиционной формальной логики, согласно которому из двух формально противоречащих друг другу мыслей одна обязательно должна быть истинной, а вторая ложной.) В математической логике закон исключенного третьего выражается формулой где  — знак дизъюнкции,  — знак отрицания.

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

10

Равные логические функции

Функции, которые при одинаковых наборах значений входящих в них переменных, принимают одинаковые значения.

№ п/п

Новые понятия

Содержание

1

Множество

Является фундаментальным понятием в математике, но не имеет четкого определения, но относительно множества можно сказать, что оно состоит из элементов

2

Подмножество

Состоит из элементов множества, мощность которого меньше мощности множества. Мощность множества- количество элементов в множестве.

3

Конечное множество

Множество, количество элементов которого конечно, то есть, существует неотрицательное целое число, равное количеству элементов этого множества

4

Пустое множество

Множество, не содержащее ни одного элемента. Пустое множество является своим ( тривиальным )  подмножеством, но не является своим элементом.

5

Равные множества

Множества, которые состоят из одних и тех же элементов, т. е. если каждый элемент множества 1 принадлежит множеству 2 и, обратно, каждый элемент множества 2 принадлежит множеству 1. Тогда пишут 1 = 2.

6

Мощность множества

Количество элементов в множестве.

7

Объединение множеств

Множество, содержащее в себе все элементы исходных множеств.

8

Пересечение множеств

Множество, которому принадлежат те и только те элементы, которые одновременно принадлежат всем данным множествам.

9

Разность множеств

Множество, в которое входят все элементы первого множества, не входящие во второе множество

10

Булеан множества

Множество всех возможных подмножеств данного множества

11

Декартово произведение множеств

Способ конструирования новых объектов из уже имеющихся множеств.

A*B={ (a,b)| a € A и b € B}

12

Правило суммы

Если некоторый объект А можно выбрать m способами, а другой объект В можно выбрать nспособами, то выбор "А или В" можно осуществить m+n способами.

13

Правило произведения

Если некоторый объект A может быть выбран из совокупности объектов M способами и после каждого такого выбора другой объект B может быть выбран N способами, то пара объектов (A,B) в указанном порядке может быть выбрана (M*N) способами.

14

Принцип двойственности

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

15

Диаграммы Эйлера-Венна

Позволяют наглядно изобразить взаимодействие множеств. Для построения необходимо:

1.Изобразить прямоугольник(Универсум)

2.В прямоугольнике изобразить круги, пересекающиеся между собой(кол-во кругов определяется операциями)

3.Заштриховать области соответствующие операциям