Глава 1. Логика высказываний — КиберПедия 

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

Двойное оплодотворение у цветковых растений: Оплодотворение - это процесс слияния мужской и женской половых клеток с образованием зиготы...

Глава 1. Логика высказываний

2017-07-01 1337
Глава 1. Логика высказываний 0.00 из 5.00 0 оценок
Заказать работу

Глава 1. Логика высказываний

 

Основные понятия

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

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

 

Основными логическими операциями над высказываниями являются: отрицание, конъюнкция, дизъюнкция, импликация, эквивалентность, неравнозначность.

Отрицанием (инверсией) высказывания P называется высказывание, истинное тогда и только тогда, когда высказывание P ложно, и ложное в противном случае. Обозначения: , ù P. Читается: «не P». Отрицание определяется таблицей истинности (табл. 4.1).

Конъюнкцией (операцией «И», логическим произведением) двух высказываний P и Q называется высказывание, истинное тогда и только тогда, когда истинны оба высказывания, и ложное во всех других случаях. Обозначения: P&Q, P×Q, PÙQ. Читается: «P и Q». Конъюнкция определяется таблицей истинности (табл. 4.2).

Дизъюнкцией (операцией «ИЛИ», логической суммой) двух высказываний P и Q называется высказывание, ложное тогда и только тогда, когда оба высказывания ложны, и истинное – во всех других случаях. Обозначения: PÚQ, P+Q. Читается: «P или Q» (понимается как неразделительное «или»). Дизъюнкция определяется таблицей истинности (табл. 4.3).

 

Импликацией (логическим следованием) двух высказываний P и Q называется высказывание, ложное тогда и только тогда, когда P истинно, а Q ложно, и истинное – во всех других случаях. Обозначения: P®Q, PÉQ. Читается: «если P, то Q», «P влечет Q»). Высказывание P называется посылкой импликации, а высказывание Q - заключением. Импликация определяется таблицей истинности (табл. 4.4).

 

Эквивалентностью (равнозначностью, эквиваленцией) двух высказываний P и Q называется высказывание, истинное тогда и только тогда, когда истинностные значения P и Q совпадают, и ложное в противном случае. Обозначения: P«Q, P~Q, PºQ. Читается: «P эквивалентно Q», «P, если и только если Q», «P равнозначно Q». Эквивалентность определяется таблицей истинности (табл. 4.5).

Неравнозначностью (исключающим «ИЛИ», сложением по модулю 2) двух высказываний P и Q называется высказывание, истинное тогда и только тогда, когда истинностные значения P и Q не совпадают, и ложное – в противном случае. Обозначения: PÅQ, PDQ. Читается: «P неравнозначно Q», «либо P, либо Q», «или P, или Q» (понимается – в разделительном смысле). Неравнозначность определяется таблицей истинности (табл. 4.6).

 

Буквы, обозначающие высказывания, логические связки и скобки, составляют алфавит языков логики высказываний: алгебры логики и исчисления высказываний.

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

- любая переменная, обозначающая высказывание, - формула;

- если P и Q – формулы, то P&Q, PÚQ, P®Q, P«Q, PÅQ – формулы;

- других формул нет.

Пример 4.1. Представить логическими формулами следующие высказывания:

1. «Сегодня понедельник или вторник».

2. «Идет дождь или снег».

3. «Если идет дождь, то крыши мокрые. Дождя нет, а крыши мокрые».

4. «Что в лоб, что по лбу».

Решение.

1. Составное (сложное) высказывание «Сегодня понедельник или вторник» состоит из двух простых:

P – «Сегодня понедельник»; Q – «Сегодня вторник».

Высказывания P и Q соединены связкой «или» в разделительном смысле. Поэтому данное высказывание представимо логической формулой: PÅQ.

2. Составное высказывание «Идет дождь или снег» состоит из двух простых:

P – «Идет дождь»; Q – «Идет снег».

Высказывания P и Q соединены связкой «или» не в разделительном, а в обычном смысле. Таким образом, логическая формула имеет вид: P Ú Q.

3. Первое предложение «Если идет дождь, то крыши мокрые» включает два простых высказывания:

P – «Идет дождь»; Q – «Крыши мокрые».

Высказывания P и Q соединены связкой «если ¼, то ¼»: P ® Q.

Второе предложение «Дождя нет, а крыши мокрые» также как и первое включает высказывания:

P – «Идет дождь»; Q – «Крыши мокрые».

Союз “а” имеет смысл связки «и», кроме того высказывание P используется с отрицанием, т.е. второе предложение представляется в виде: & Q.

Далее, объединяем оба предложения в одно высказывание связкой &: (P ® Q) &( & Q).

4. Составное высказывание «Что в лоб, что по лбу» состоит из двух простых:

P – «В лоб»; Q – «По лбу».

Высказывания P и Q соединены связкой «равнозначно»: P «Q.


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

 

 

 

Предикаты

 

 

 


 

Множества

 

Множество относится кпервоначальным понятиям науки, не определяемым через другие, более простые термины. Множество представляет собой определенную совокупность объектов, объединенных в единое целое в соответствии с некоторыми признаками и правилами. Множества обозначаются: A, B, C, X, Y, Z. Примеры множеств:

· множество всех атомов на Марсе;

· множество точек окружности;

· множество решений заданного уравнения;

· множество всех действительных чисел - R.

 

Г. Кантор (1845–1918 гг.) определял Множество как «многое, понимаемое как единое».

Наконец, определение Множества как «совокупности определенных различаемых объектов». Здесь для «объекта» важен просто сам факт принадлежности к Множеству – своеобразное характеристическое свойство.

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

Множества обозначаются обычно большими латинскими буквами (необязательно), в их определении используется фигурные скобки ({}). Например, M = {a, b, c }.

Здесь определено 3-элементное множество путем простого перечисления элементов.

Еще пример, множество натуральных чисел: N = {1, 2, 3, …}.

Это бесконечное множество (о других его определениях еще придется говорить).

Рис. 1. Диаграмма Венна

Для пересечения множеств

Объединение множеств (рис. 2): А È В = {х: х Î А или х Î В}.

«È» похоже на незавершенную русскую букву «О» («объединение»). ИЛИ здесь – не исключительное, т. е. это аналог «обычной» нестрогой дизъюнкции. Есть еще строгая дизъюнкция (ИЛИ-ИЛИ), в логике она обозначается «».

 

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

 

Утверждение: Для любых множеств А и В мощность объединения

çА Вç=çАç+çВç-çА Вç

Первые две операции фактически обладают теми же свойствами, что и операции &, v в алгебре логики.

Например, они коммутативны: А * В = В * А, и это, вообще-то, свойство логических связок «и», «или».

Они идемпотентны: А * А = А.

Свойство идемпотентности позволяет произвольно сжимать или расширять выражения, что весьма полезно в разного рода преобразованиях.

Кстати, {1, 2} Ç {2, 3} = {2},

{1, 2} È {2, 3} = {1, 2, 3},

но

{{1, 2}, {2, 3}} ¹ {1, 2, 3}!

Разность двух множеств А \ В = {х: х Î А и х Ï В}. (рис. 3):

Рис. 3. Разность двух множеств

 

Заштрихованная область на рис. 3 соответствует дополнению В до А. Аналогично можно определить разность В \ А, или дополнение А до В (область В на рис. 3 без общей части).

Симметрическая разность (рис. 4): А D В = (А È В) \ (А Ç В).

 

Рис. 4. Симметрическая разность

 

Как видно, здесь реализуется исключительное ИЛИ (строгая дизъюнкция). В алгебре логике существует аналог: А Å В = (А v В) .

Действительно, (А v В) = (А v В) (`А v `В) = А`В v `АВ = А Å В.

Дополнение множества (до универсального): А¢ = Е \ А = {х: х Ï А}.

Множество и его дополнение однозначно определяются двумя равенствами (используются в доказательствах):

А Ç А¢ = Æ,

А È А¢ = Е.

Рис. 6. Диаграмма Венна

Элементы комбинаторики

Принцип сложения

Если выбор А можно осуществить n способами, а выбор В можно осуществить m способами, то выбор либо А, либо В можно осуществить m+n способами, в случае если при выборе способов нет совпадений, если k – число совпадений, то выбор либо А либо В можно осуществить m+n-k способами.

 

Принцип умножения

Пусть выбор А можно осуществить n способами, а выбор В - m способами, тогда выбор А и В можно осуществить m*n способами.

 

Решим задачу.

1.Из Ростова-на-Дону до Москвы можно добраться пароходом, поездом, автобусом и самолетом. Из Москвы до Санкт-Петербурга поездом, автобусом и самолетом. Сколькими способами можно осуществить путь по маршруту Ростова-на-Дону – Москва - Санкт-Петербург.

 

Ростова-на-Дону пароходом Москва поездом Санкт-Петербург
поездом автобусом
автобусом самолетом
самолетом  

4*3=12

Выбор А*В можно осуществить 12 способами.

 

2.В стране чудес есть 4 города А, В, С, Д. Из города А в город В ведет 6 дорог, из В в Д – 4, из А в С – 2, из С в Д – 3. Сколькими способами можно проехать от А до Д.

А   В
     
С   Д

2*3+6*4=30

 

Соединения без повторений

 

Соединение предметов
 
Размещение из n элементов по k элементам (важен порядок и важны сами элементы) Перестановка n элементов без повторения (важен порядок, элементы не важны) Сочетание из n элементов по k элементам (важны элементы, порядок не важен)

 

Определение: Введем множество N0=NÈ{0}.Пусть элементы k, n ÎN0, причем k£n. Размещением из n элементов множества В={b1, b2,…, bn} по k элементам будем называть всякую последовательность, составленную из неповторяющихся элементов множества В, имеющую длину k

1, а2, …, аk).

Пример: А ={1,2,3}. Выпишем все размещения из трех элементов по 2

(1,2); (1,3); (2,1); (2,3); (3,1); (3,2)

Теорема Пусть дано множество В={b1, b2,…, bn} k, n ÎN0, k£n. Число размещений из n элементов по k элементам без повторений можно вычислить по формуле:

=

Для доказательства воспользуемся принципом умножения. Для построения каждого размещения нужно рассмотреть последовательность из n элементов. На первом месте n возможностей, на втором n-1.

Пусть (n-k)!=1*2*3*…(n-k) n!=1*2*3*…*(n-k)*(n- k +1)*…*n

Определение: Пусть N0=NÈ{0}, k, n ÎN0, k£n, В={b1, b2,…, bn}. Сочетанием из n элементов по k элементам без повторений будем называть всякое подмножество множества В, состоящее из k неповторяющихся элементов заданного множества В.

Пример: А ={0,1,4}. Выпишем все размещения из трех элементов по 2

{0,1}; {1,4};{ 0,4}

 

Теорема Пусть k, n ÎN0, k£n, В={b1, b2,…, bn}. Число сочетаний из n элементов по k элементам можно подсчитать используя формулу:

Рассмотрим формулу из предыдущей теоремы. Число размещений равно . Ясно, что число размещений можно связать с числом сочетаний формулой . следовательно .

Задача: Сколькими способами можно рассадить 4 учащихся на 25 местах.

I способ (принцип умножения)

25*24*23*22=303600

II способ (размещение)

Задача: Учащемуся необходимо сдать 4 экзамена на протяжении 8 дней. Сколько способов? Решить задачу если известно, что последний экзамен будет сдаваться на 8 день.

1)

2) 4*

Задача: Сколькими способами читатель может выбрать 3 книги из 5.

Задача: В турнире принимали участие n шахматистов, каждые два шахматиста встретились 1 раз. Сколько партий было в турнире?

Определение: Пусть n ÎN0, В={b1, b2,…, bn}. Перестановкой n элементов множества В будем называть всякое размещение без повторений из n элементов по n элементам.

Теорема . Число перестановок n элементов множества равно n! n ÎN0, В={b1, b2,…, bn}.

Пусть

Следствие: n, k ÎN0, k£n, В={b1, b2,…, bn}. Число размещений из n элементов по k элементам модно вычислить по формуле:

Задача: Сколькими способами можно разместить в очередь 7 человек.

N=7 Р7=7!

Задача: Сколькими способами можно упорядочить множество 1, 2, 3, …, 2n, так чтобы каждое четное число имело четный номер.

А ={1, 2, 3, …, 2n} n!*n!=(n!)2.

 

Задача: Сколько можно составить перестановок из n элементов, в которых данные два элемента не стоят рядом.

n!-(n-1)!2!=(n-1)!(n-2)

Свойства сочетаний

(из7)

Из св 6 можно последовательно находить зная . в виде треугольника Паскаля:

 

Формула бинома Ньютона

(а+b)n= (можно доказать по индукции)

Перемножим (а+b) само на себя n раз, получим сумму, содержащую 2n слагаемых, каждое слагаемое представляет произведение d1*d2*…*dn, где di либо а, либо b, , полученную сумму разобьем на n+1 слагаемых В0, В1, …Вn.

Пусть у нас в группе Вk содержатся те произведения, в которых элемент b встречается k раз, а элемент a встречается (n-k) раз.

 

Полиномиальная теорема

 

12+…+аk)n=

Перемножим сумму k слагаемых на себя n раз

12+…+аk)… (а12+…+аk), получим kn слагаемых вида d1d2…dn, где каждый множитель di равен либо а12,…,аk. Обозначим В(r1, r2, …,rk) совокупность всех тех слагаемых, в которых элемент а1 встречается r1 раз, а2 встречается r2 раза, аk встречается rk раз. Число таких слагаемых равно

Пусть элемент а повторяется r раз, элемент b – (n-r) раз соответственно, полиномиальный коэффициент

Рn(r,n-r)=

Упражнение: Покажите, что

 

Отношения. Основные понятия

Отношения – это один из способов задания взаимосвязей между элементами множества. Наиболее распространены унарные и бинарные отношения.

Унарные (одноместные) отношения отражают наличие какого-либо определенного признака R у элементов множества A.

Все элементы множества A, обладающие признаком R, образуют некоторое подмножество: AR = ía: aÎA & aÎRý.

Бинарные (двухместные) отношения используются для определения взаимосвязей, которыми характеризуются пары элементов множества A. Например, на множестве людей могут быть заданы следующие бинарные отношения: «жить в одном городе», «учиться в одном институте».

В общем случае отношения могут быть n-местными. Под n-местным отношением понимают подмножество R прямого произведения n множеств:

RÍM1´M2´¼´Mn.

Бинарным отношением R называется подмножество пар (a,b) Î R декартового произведения M1´M2, где R Í M1´M2. Множество M1 – область определения отношения R, множество M2 – область значений отношения R.

Если задано отношение R между парами элементов одного и того же множества M, то R Í M´M.

Вместо записи (a,b) Î R используют также обозначение a R b.

Шахматная доска доставляет пример бинарного отношения на множестве горизонталей G = {1, 2, …, 8} и множестве вертикалей W = {a, b, …, h}. В результате получается множество клеток доски: D = W * G = {(a, 1), (a, 2), …, (h, 8)}, |D| =64.

Выделяются три отношения:

пустое отношение, Æ Í М2;

универсальное отношение, UM = {(x, y): x, y Î M};

тождественное отношение, IM = {(x, x): x ÎM}.

Область D(R) определения и область значений Q(R) отношения R определяются в виде:

D(R) = ía: (a,b)ÎRý, Q(R) = íb: (a,b)ÎRý.

Задать бинарные отношения можно любым способом задания множеств:

1) В виде характеристического свойства R = í(a,b): (a,b)ÎRý, где в правой части равенства вместо R записывается характеристическое свойство.

2) Списком (перечислением) пар, для которых выполняется данное отношение. Например, R = í(a,b), (a,d), (b,c)ý.

3) Матрицей. Отношению R Í M´M, где M = ía1, a2, ¼, aný, соответствует квадратная матрица порядка n, в которой элемент cij, стоящий на пересечении i-й строки и j-го столбца, равен 1, если между ai и aj имеет место отношение R, или 0, если оно отсутствует:

.

Пример 2.1. Пусть M = í1, 2, 3, 4, 5ý. Задать в виде характеристического свойства, списком (в явном виде) и матрицей отношение R Í M´M, если R означает «быть меньше».

 

Решение. Отношение R как множество содержит все пары элементов a,b из M, такие что a<b. Тогда отношение R в виде характеристического свойства имеет вид:

R = í(a,b): a<b, a,bÎMý.

В виде списка отношение R выглядит следующим образом:

R = í(1,2), (1,3), (1,4), (1,5), (2,3), (2,4), (2,5), (3,4), (3,5), (4,5)ý.

Матрица отношения R приведена на рис. 2.2.

 

Можно рассмотреть несколько вариантов графического представления отношений:

– точки в плоскости D F;

 

– ориентированные отрезки (со стрелками)

от точек оси абсцисс, соответствующих левым

элементам пар, к точкам оси ординат,

соответствующих правым элементам;

– двудольный орграф

(левая доля соответствует области определения

D, правая – области значений F);

– ориентированный граф порядка, равного мощности бинарного отношения (рис. 7).

М = {1, 2, 3, 4}, R = {(1, 2), (1, 4), (2, 3), (2, 4), (3, 4), (4, 1)} (рис. 7а).

 

 

Рис. 7. Графическое представление отношений

На рис. 7б и 7в представлены также графы тождественного отношения IМ и универсального отношения UМ.


Свойства отношений

Основными свойствами отношений являются:

– рефлексивность; – симметричность; – транзитивность; – антисимметричность;

Рефлексивность означает: справедливо xrx для любого x Î M.

В графе отношения все вершины имеют петли. (например, отношение «жить в одном городе» – рефлексивно);

R – антирефлексивно, если ни для какого a Î M имеет место a R a (например, отношение «быть сыном» – антирефлексивно);

 

Симметричность: xry Þ yrx. (например, отношение «учиться в одном институте» – симметрично)

При этом может быть и «пустая» симметричность когда нет xry («на нет и суда нет»). В графе соответствия каждая дуга имеет пару, но может быть и отсутствие связи между двумя вершинами.

Транзитивность: xry и yrz Þ xrz. «быть моложе» – транзитивно

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

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

Антисимметричность: xry и yrx Þ x = y. т.е. ни для каких различных элементов a, b (a ¹ b) не выполняется одновременно a R b и b R a (например, отношения «быть сыном», «быть начальником» – антисимметричны);

 

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

асимметричность, … означает: прямые связи есть и двойные, и одинарные, и «никакие», т.е. нет ни симметричности, ни антисимметричности.

Свойства симметричности и антисимметричности не являются взаимно исключающими. Они могут “сосуществовать”. Правда, это возможно только в пустом варианте (рис. 8.)

 


Рис. 8. Примеры одновременных симметричности и антисимметричности

Отмеченные выше свойства отношений являются относительно редкими. Например, отношение, представленное графом на рис. 9, не является ни рефлексивным (P), ни симметричным (C), ни транзитивным (T) и ни антисимметричным (А).

 
 

 

 


Рис. 9. Пример отношения.

 

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

С: xry Þ yrx, А: xry и yrz Þ xrz;

при x = z получается как будто рефлексивность:

Р: xrx.

На самом деле это, конечно, не так. Убедиться в этом (доказать это) предоставляется читателю. (На примере?)

Пример: А={1,2,3}

r1={(1,1), (3,3), (1,2)} нерефлексивно, несимметрично, транзитивно

r2={(1,1), (3,3), (2,2)} рефлексивно, симметрично, транзитивно, эквивалентно на А, антисимметрично

r3={(1,2), (2,1)} антирефлексивно, симметрично, нетранзитивно

r4={(1,1), (3,3), (1,2), (2,1)} нерефлексивно, симметрично, нетранзитивно

r5={(1,1)} нерефлексивно, симметрично, транзитивно

r6={(1,2)} антирефлексивно, несимметрично, транзитивно

r7=r2È{(1,3), (3,1)} эквивалентно

r8=r2È{(1,3), (3,1), (2,3)} рефлексивно, несимметрично, нетранзитивно

 

Пусть задано некоторое множество А, разбиение будем называть U.

Определение: Совокупность подмножеств множества А будем называть разбиением данного множества, если:

1) АiÇAj=Æ, i¹j

2) .

Пример: Дано множество В=R=(-¥;1)È[1;2] È[2;¥)

А1 А2 А3

Является ли разбиением данные подмножества?

U={А123} - не является

 

Пусть задано множество В={-1;4;7}

U1={-1,{4,7}} не является разбиением

U2={{-1,4,7}} является разбиением

U3={{-1},{4},{7}} является разбиением

U4={{-1,4},{7}} является разбиением

U5={{-1,4},{4,7}} не является разбиением

 

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

Предварительно определим два таких понятия.

Покрытие множества – это совокупность его подмножеств, совместно накрывающих это непустое множество: Мi = M, М ¹ Æ.

Например, {M1, M2} является покрытием множеств M1 È M2.

Разбиение множества – частный случай покрытия, когда составляющие подмножества попарно не пересекаются: Мi = M,

Mi1 Ç Mi2 (i1 ¹ i2) = Æ.

Например, для универсального множества:

E = { М1 Ç М2, М1 Ç М2¢, М1¢ Ç М2, М1¢ Ç М2,¢}r.

Здесь индекс «r» («разбивание») обязателен, иначе получается неравенство мощностей слева и справа (справа – всего 4). В подмножествах разбиения каждый элемент M представлен только один раз.

Отношение эквивалентности – это первое замечательное теоретико-множественное отношение. Оно обладает тремя свойствами: рефлексивность, симметричность и транзитивность. По-другому говорят: любое РСТ-отношение – это отношение эквивалентности. Таковым является, например, обычное математическое равенство («=»).

Отношение эквивалентности r разбивает множество М на классы эквивалентности: M / r. Между элементами каждого такого класса существует РСТ-отношение. Класс эквивалентности обозначается с использованием квадратных скобок. Внутри указывается любой элемент класса.

Например, широко используемые в теории чисел сравнения задают разбиение множества целых чисел Z на m классов эквивалентности, где m – некоторый модуль сравнения: rm ={(x, y): x – y = k m, m Î N, k Î Z }.

При m=5 получаем: [1]={6, 11, 16, –4, 1, …},

[34]={29, 39, 4, …},

… …

Фактически различных классов эквивалентности здесь всего 5 – столько «простых» вычетов по модулю 5. Эти вычеты (остатки от деления на 5): 0, 1, 2, 3, 4.

[0] = {…, –5, 0, 5, 10, …},

[1] = {…, –4, 1, 6, 11, …},

… …

[4] = {…, –1, 4, 9, 14, …}.

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

0 º 5 (mod 5),

1 º –4 (mod 5),

… …

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

 


Отношение порядка

Это второе «замечательное» отношение (в математическом анализе есть второй замечательный предел, определяющий константу e = 2,71828…: ).

Частичный порядок на множестве M – это любое рефлексивное, транзитивное и антисимметричное (РТА-) отношение. В обычной математике ему соответствует отношение нестрогого неравенства «£».

Наиболее важное свойство отношения порядка – его транзитивность.

Кстати, отношение £ и < (строгое неравенство) связаны очень просто:

а < b Û а £ b и а ¹ b, а £ b Û а < b или а = b.

Видно, что отношение строгого порядка нерефлексивно.

Полное отношение порядка r на M означает, что для любых элементов x, y Î M выполняется xry и/или yrx, причем r – это РТА- отношение.

В связи c упорядочиванием элементов вводится множество таких понятий:

верхняя граница элементов x, y (u Î M, x £ u, y £ u);

нижняя граница элементов x, y (v Î M, v £ x, v £ y);

верхняя грань элементов x, y («супремум»); m Î M, m £ "u; здесь верхних границ u – множество; m = sup (x, y));

нижняя грань элементов x, y («инфимум»; n Î M, "v £ n; n = inf (x, y));

замкнутый интервал значений ([a, b] = {x: x Î R, a £ x £ b });

открытый интервал (] a, b [ = { x: x Î R, a < x < b});

полуоткрытый интервал (] a, b ] = { x: x Î R, a < x £ b} или [ a, b [ = {x: x Î R,

a £ x < b});

концевые точки интервала (a, b).


Глава 1. Логика высказываний

 

Основные понятия

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

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

 

Основными логическими операциями над высказываниями являются: отрицание, конъюнкция, дизъюнкция, импликация, эквивалентность, неравнозначность.

Отрицанием (инверсией) высказывания P называется высказывание, истинное тогда и только тогда, когда высказывание P ложно, и ложное в противном случае. Обозначения: , ù P. Читается: «не P». Отрицание определяется таблицей истинности (табл. 4.1).

Конъюнкцией (операцией «И», логическим произведением) двух высказываний P и Q называется высказывание, истинное тогда и только тогда, когда истинны оба высказывания, и ложное во всех других случаях. Обозначения: P&Q, P×Q, PÙQ. Читается: «P и Q». Конъюнкция определяется таблицей истинности (табл. 4.2).

Дизъюнкцией (операцией «ИЛИ», логической суммой) двух высказываний P и Q называется высказывание, ложное тогда и только тогда, когда оба высказывания ложны, и истинное – во всех других случаях. Обозначения: PÚQ, P+Q. Читается: «P или Q» (понимается как неразделительное «или»). Дизъюнкция определяется таблицей истинности (табл. 4.3).

 

Импликацией (логическим следованием) двух высказываний P и Q называется высказывание, ложное тогда и только тогда, когда P истинно, а Q ложно, и истинное – во всех других случаях. Обозначения: P®Q, PÉQ. Читается: «если P, то Q», «P влечет Q»). Высказывание P называется посылкой импликации, а высказывание Q - заключением. Импликация определяется таблицей истинности (табл. 4.4).

 

Эквивалентностью (равнозначностью, эквиваленцией) двух высказываний P и Q называется высказывание, истинное тогда и только тогда, когда истинностные значения P и Q совпадают, и ложное в противном случае. Обозначения: P«Q, P~Q, PºQ. Читается: «P эквивалентно Q», «P, если и только если Q», «P равнозначно Q». Эквивалентность определяется таблицей истинности (табл. 4.5).

Неравнозначностью (исключающим «ИЛИ», сложением по модулю 2) двух высказываний P и Q называется высказывание, истинное тогда и только тогда, когда истинностные значения P и Q не совпадают, и ложное – в противном случае. Обозначения: PÅQ, PDQ. Читается: «P неравнозначно Q», «либо P, либо Q», «или P, или Q» (понимается – в разделительном смысле). Неравнозначность определяется таблицей истинности (табл. 4.6).

 

Буквы, обозначающие высказывания, логические связки и скобки, составляют алфавит языков логики высказываний: алгебры логики и исчисления высказываний<


Поделиться с друзьями:

Наброски и зарисовки растений, плодов, цветов: Освоить конструктивное построение структуры дерева через зарисовки отдельных деревьев, группы деревьев...

Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...

Своеобразие русской архитектуры: Основной материал – дерево – быстрота постройки, но недолговечность и необходимость деления...

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



© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!

0.315 с.