Главная / Темы / Логика. Основные сведения.

Логика. Основные сведения.

1. Элементарные высказывания.

2. Логические значения, логические связки и логические выражения.

3. Свойства логических выражений и таблиц истинности. 

4. Эквивалентные преобразования логических выражений. 

5. Высказывания о множествах

6. Примеры эквивалентных преобразований

 

1. Элементарные высказывания

1.1.Истинные и ложные высказывания.

Утверждения (они же: высказывания) об объектах окружающего мира строятся из элементарных  высказываний. Такие высказывания утверждают что-то о свойствах объекта или об отношениях между объектами (чаще всего – между двумя объектами).

Примеры.

  1. Забор красный. Здесь забор – объект, а красный описывает его свойство. «красный» (иногда говорят – свойство «быть красным»).  Имеется в виду конкретный забор, а не забор вообще!  В русском языке свойства часто (но не всегда) выражаются прилагательными.
  2. Коля и Петя – друзья. Здесь Коля и Петя – «объекты», а слово друзья описывает отношение между ними. Это отношение симметрично – смысл сказанного не поменяется, если написать   «Петя и Коля – друзья». Здесь, как и во всех элементарных высказываниях, имеются в виду конкретные люди.
  3. Коля старше, чем Петя. Здесь отношение описывается словами «старше, чем». Это отношение не является симметричным.

Высказывание может быть истинным (верным) или ложным (неверным). Например, Коля может на самом деле быть старше, чем Петя (тогда высказывание 3 истинно). А, может быть, Коля младше Пети, или они одного возраста. Тогда это высказывание ложно.

 1.2. Объекты, свойства и отношения в математике.

В математике мы имеем дело с математическими объектами, их свойствами и отношениями. Примеры математических объектов: числа: натуральные, целые, рациональные (они же - обыкновенные дроби), вещественные; точки, прямые,  множества. С числами, точками и прямыми вы познакомились на уроках математики. Про множества коротко написано здесь.

Вот примеры свойств, отношений и высказываний для целых чисел (при описании свойств и отношений вместо чисел стоят многоточия…) .

Свойства: … - четное; … - нечетное, … - положительное.

Примеры высказываний: (1) 4 – четное. (2)  4 – нечетное.  (3) 4 – положительное.  Здесь первое и третье высказывание истинны, а второе – ложно.

Отношение: …больше, чем …; … меньше, чем…;  … делится на … .

Примеры высказываний: (1) 4 больше, чем 2. (2)  4 меньше, чем 2.  (3) 4 делится на 2.  Здесь тоже первое и третье высказывание истинны, а второе – ложно.

В математике отношения часто записываются специальными знаками. Например, 6 < 3. 

Замечание. Вместо «явного» обозначения, например, чисел в высказываниях можно использовать и выражения, значениями которых являются числа. Пример:

(2+ 3) < (2*3)

Смысл таких высказываний ясен: нужно вычислить значения выражений и получится уже знакомое нам истинное высказывание о числах: 5 < 6   Точно так же можно использовать выражения, например, с множествами, используя, операции объединения, пересечения, разности, дополнения (см. подробнее здесь).

1.3.  Утверждения всеобщности.

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

a+b = b+a

Здесь имеется в виду вот что. Для любых чисел, если их подставить вместо a и b, получится истинное высказывание. То есть, истинны все указанные ниже высказывания и еще бесконечно много подобных им высказываний:

27 + 12 = 12 + 27 (вместо a подставили 27, вместо b подставили 12)

2 + 5 = 5 + 2 (вместо a подставили 2, вместо b подставили 5)

5 + 2 = 2 + 5 (вместо a подставили 5, вместо b подставили 2)

5 + 5 = 5 + 5 (вместо a подставили 5, вместо b  тоже подставили 5)

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

2. Логические значения, логические связки и логические  высказывания

2.1. Составные высказывания

Из элементарных высказываний можно строить более сложные (составные) высказывания, используя связки И, ИЛИ, НЕ.

Примеры.      Забор красный И забор деревянный.

Коля старше, чем Петя ИЛИ Коля старше, чем Федя

Забор НЕ красный.

Смысл этих высказываний понятен.

Высказывание с И содержит два элементарных высказывания. Составное высказывание с И истинно тогда и только тогда, когда истинны оба эти элементарные высказывания. Если хоть одно из них ложно, - составное высказывание ложно.

Высказывание с ИЛИ тоже содержит два элементарных высказывания. Составное высказывание с ИЛИ истинно тогда и только тогда, когда истинно хотя бы одно из этих элементарных высказываний. Если оба эти высказывания ложны, - составное высказывание ложно.

Высказывание с НЕ содержит одно элементарное высказывание (в русском языке НЕ часто ставится в середину этого высказывания). Составное высказывание с НЕ истинно, если исходное элементарное высказывание ложно и, наоборот,  если исходное высказывание истинно, то составное высказывание с НЕ  ложно.

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

(Коля старше, чем Петя ИЛИ Коля старше, чем Федя) И (Коля НЕ старше, чем Ваня)

Здесь 3 элементарных высказывания.

2.2. Логические значения. Логические операции.

Мы уже знаем, что каждому высказыванию можно приписать одно из двух логических значений ­истина (часто обозначается: 1) или ложь (часто обозначается: 0).  Слова И, ИЛИ, НЕ задают операции над логическими значениями (логические операции). Действительно, например, составное высказывание с И истинно тогда и только тогда, когда истинны оба его элементарные высказывания. Если хоть одно из них ложно, - составное высказывание ложно. Здесь нам не важно, каковы были исходные высказывания. Истинность составного высказывания зависит только от логического (иногда говорят - истинностного) значения исходных высказываний.

Так как логических значений всего два, то эти операции можно описать таблицами.

Fig02

У операций И, ИЛИ, НЕ есть «научные» названия (даже несколько для каждой операции :) и специальные обозначения (в примерах A, B обозначают какие-то конкретные логические значения):

НЕ: отрицание, инверсия. Обозначение: ¬ (например, ¬А);

И:   конъюнкция, логическое умножение.

       Обозначается /\ (например, А /\ В) либо & (например, А & В);

ИЛИ: дизъюнкция, логическое сложение.

Обозначается \/ (например, А \/ В).

В математике используются и другие логические операции.

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

1) следование (импликация); обозначается → (например, А → В).  Выражение А → В истинно если A ложно ИЛИ B истинно. То есть, А → В означает то же самое, что и (¬А) \/ В. См. таб. 4.

2) тождество (эквивалетность); обозначается ≡ (например, A ≡ B). Выражение A ≡ B истинно тогда и только тогда, когда значения A и B совпадают (либо они оба истинны, либо они оба ложны). См. таб. 5.

Fig03

2.3. Логические выражения.  Таблицы истинности.

Логические операции играют для логических значений ту же роль, что и арифметические операции для чисел. Аналогично построению алгебраических выражений, с помощью логических операций можно строить логические выражения. Как и алгебраические выражения, логические выражения могут включать константы (логические значений 1 и 0) и переменные. Если в логическом значении есть переменные, оно задает функцию (логическую функцию; синоним: булеву функцию). Значение такой функции при заданном наборе значений аргументов вычисляется подстановкой этих значений в выражение вместо переменных.

Для каждого логического выражения можно составить таблицу истинности, которая описывает, какое значение принимает соответствующая логическая функция (синоним: принимает выражение) при каждом допустимом наборе значений переменных. Каждая строка таблицы истинности соответствует одному возможному набору аргументов логической функции. Поэтому таблица истинности для логической функции от n переменных содержит 2n строк. В каждой строке таблицы истинности указывается набор значений переменных и значение функции, соответствующее этому набору. Вот таблицы истинности для выражений x \/ y (таблица 6),  x → y (таблица 7) и  (x → y) /\ (y → z) (таблица 8).

 Fig06

.

 

.

 

 

 

2.4. Приоритеты логических операций.

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

отрицание (инверсия),

конъюнкция (логическое умножение),

дизъюнкция (логическое сложение),

импликация (следование),

тождество.

Таким  образом,  ¬А \/ В \/ С \/ D  означает  то  же,  что и ((¬А) \/ В)\/ (С \/ D).

Возможна запись А \/ В \/ С вместо (А \/ В) \/ С. То же относится и к конъюнкции: возможна  запись А /\ В /\ С вместо  (А /\ В) /\ С.

Упражнения.

 

3. Свойства логических выражений и таблиц истинности. 

Приведенный ниже список НЕ претендует на полноту, но, надеемся, достаточно представителен.

3.1. Общие свойства

1) Для n логических переменных существует ровно 2n различных наборов значений.

2) Таблица истинности для логического выражения от n переменных содержит n+1 столбец (по одному столбцу на каждую переменную + 1 столбец на значение выражения) и  2n строк (по одной строке на каждый набор значений переменных).

3.2.Дизъюнкция

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

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

3) Значение дизъюнкции не зависит от порядка записи выражений, к которым она применяется.

4) При вычислении дизъюнкции выражений эти выражения можно группировать как угодно - значение дизъюнкции не изменится.

5) Пусть все выражения, к которым применяется дизъюнкция, - это различные переменные или их отрицания. Тогда существует ровно один набор значений переменных, при которых дизъюнкция ложна. Переменная в этом наборе имеет значение 1, если в дизъюнкцию она входит с отрицанием и значение 0 в противном случае.

3.3. Конъюнкция

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

2) Если все выражения из некоторого списка истинны на некотором наборе значений переменных, то конъюнкция этих выражений тоже истинна.

3) Значение конъюнкции не зависит от порядка записи выражений, к которым она применяется.

4) При вычислении конъюнкции выражений эти выражения можно группировать как угодно - значение конъюнкции не изменится.

5) Пусть все выражения, к которым применяется конъюнкция, - это различные переменные или их отрицания. Тогда существует ровно один набор значений переменных, при которых конъюнкция истинна. Переменная в этом наборе имеет значение 1, если в конъюнкцию она входит без отрицания и значение 0 в противном случае.

3.4. Импликация

1) Импликация A →B равносильна дизъюнкции (¬А)  \/ В. Эту дизъюнкцию можно записать и так: ¬А \/ В.

2) Импликация A →B принимает значение 0 (ложь) только если A=1 и B=0. Если A=0, то импликация A→B истинна при любом значении B. Если B=1, то импликация A→B истинна при любом значении A.

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

1) Эквивалентность A ≡ B равносильна конъюнкции двух импликаций: A→B  и B→A. Эту конъюнкцию можно записать так: (A→B)/\ (B→A)

2) Эквивалентность A ≡ B принимает значение 1 (истина) тогда и только тогда, когда значения переменных A и B одинаковы, т.е. A=B=1 или A=B=0.

Поэтому эквивалентность A ≡ B равносильна выражению (A/\B) \/ ((¬А) /\ (¬В) ).

3) Эквивалентность A ≡ B принимает значение 0 (ложь) тогда и только тогда, когда значения переменных A и B различны, т.е. A=0, а B=1 или A=1, а B=0. Поэтому эквивалентность A ≡ B равносильна выражению ¬ ( (A/\¬B) \/ (А /\¬В) )

3.6. Построение выражения с заданной таблицей истинности

Для любого множества наборов значений переменных можно построить выражение, которое истинно на всех наборах из заданного множества и только на них. Это выражение удобно записать в виде дизъюнкции конъюнкций, причем в каждой конъюнкции (а) каждый член – это простая переменная или ее отрицание и при этом (б) содержатся все переменные.

Пример. На рисунке приведены все строки таблицы истинности функции F(x, y, z), при которых F(x, y, z) истинно.

Fig01

Тогда функция F может быть задана таким выражением:

x/\y/\z) \/ (x/\¬y/\z) \/ (x/\y/\¬z)

Здесь первый член дизъюнкции соответствует первой строке таблицы фрагмента истинности; второй член – второй строке; третий член – третьей строке.

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

 

4. Эквивалентные преобразования логических выражений

4.1. Эквивалентные выражения.

Два логических выражения, содержащих переменные, называются равносильными (эквивалентными), если значения этих выражений совпадают при любых значениях переменных. Так, выражения А → В и (¬А) \/ В равносильны, а   А/\В и А \/ В – нет (значения выражений разные, например, при А = 1, В = 0).

Эквивалентные выражения имеют одинаковые таблицы истинности, а у неэквивалентных выражений таблицы истинности различны.

Понятие эквивалентности для логических выражений полностью аналогично понятию эквивалентности для алгебраических выражений.

4.2. Эквивалентные (тождественные) преобразования выражений.

Выяснить, эквивалентны ли два выражения, можно сравнив их таблицы истинности. Но это не всегда удобно: построение таблицы истинности - громоздкая задача. Кроме того, часто нужно не просто проверить, эквивалентны ли два данных логических выражения, а построить для данного выражения эквивалентное ему выражение, имеющее заданный вид.  Например, бывает удобно представить выражение в виде дизъюнкции или в виде импликации (см. здесь). Аналогия для алгебраических выражений: разложить на множители выражение x2-y2 (ответ: (x-y)*(x+y) ).

Замена выражения на другое выражение, эквивалентное ему, называется эквивалентным (синоним: тождественным) преобразованием.

Основное правило тождественных преобразование - это правило подстановки: если в выражении A  заменить подвыражение P на эквивалентное ему выражение Q, то полученное новое выражение B будет эквивалентно исходному выражению A.

Правило подстановки работает и для логических, и для алгебраических выражений.

Пример 1.  Рассмотрим выражение A  = (x→y)∨z . Заменим подвыражение P = x→y на эквивалентное ему по определению выражение Q = ¬x∨y. Заменяем в A выражение P выражением Q. Получим выражение B = (¬x∨y)∨z. Выражение B эквивалентно выражению A. Учитывая приоритеты выполнения логических операций, выражение B можно записать и так: ¬x∨y∨z.

4.3. Основные логические тождества.

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

В таблице 1 приведен набор логических тождеств (пар эквивалентных логических выражений), которые полезно знать, сдавая ЕГЭ. Это не значит, что другие элементарные тождества вам не понадобится. Мы просто надеемся, что вы сможете при необходимости  вывести другие понадобившиеся тождества. Желательно уметь пользоваться этими формулами так же свободно, как, например, алгебраическими формулами сокращенного умножения. Деление формул в таблице на группы – условное и приведено лишь для удобства восприятия.

Примечание. В таблицах использована «алгебро-подобная» система обозначений логических операций. Конъюнкция (логическое умножение) и дизъюнкция (логическое сложение) обозначаются символами «·» и «+» соответственно, а отрицание – чертой сверху. Эти обозначения общеприняты среди инженеров (но не специалистов по математической логике :)) и используются в некоторых школьных учебниках, в частности, в учебниках К.Ю.Полякова и Е.А.Еремина

Таблица 1.

Fig07Fig08Fig09

 

 

 

5. Высказывания о множествах

Логические выражения над элементарными высказываниями о множествах (высказывания вида "A=∅", "xA"  "AB" )  можно преобразовывать, используя не только общие правила преобразования логических выражений, но и свои правила, связанные со свойствами операций над множествами. Ниже U - это универсальное множество; - его произвольный элемент, A, B, X - множества.  Верны следующие утверждения.

1. Следующие высказывания эквивалентны, т.е. имеют одинаковые логические значения при любых x, A, B (это обозначено знаком ⇔)

             1а) (xA)∧(xB) ⇔ xAB

             1б) (xA)∨(xB) ⇔ xAB

1в) ¬(xA) ⇔ xU\A

1г)  (xA)∧ (¬(xB)) ⇔ xA\B

2. Следующие высказывания эквивалентны, т.е. имеют одинаковые логические значения при любых X, A, B (это обозначено знаком ⇔)

             2а) (X∩A  ≠Ø ) ∨ (X∩B  ≠Ø ) ⇔ (X∩ (AB)  ≠Ø )

             2б) (X∩A  = Ø ) ∧ (X∩B  = Ø ) ⇔ (X∩ (AB)  = Ø )

  3.  (а) Пусть A ⊆ B, т.е.  A - подмножество B; x - элемент универсального множества U. Тогда истинно высказывание:

 (x ∈ A) → (x∈ B) 

(б) Пусть высказывание (x ∈ A) → (x∈ B)  истинно при любом x ∈ U. Тогда  A ⊆ B.

4.  (а) Пусть A ⊆ B, т.е.  A - подмножество B; X ⊆  U - произвольное множестваТогда истинно высказывание:

(X∩A  ≠Ø )  (X∩B  ≠Ø )

(б) Пусть высказывание (X∩A  ≠Ø )  (X∩B  ≠Ø )  истинно для любого множества X ⊆  U. Тогда  A ⊆ B.

5. Следующее высказывания истинны для любых множеств A, B, X

( (X∩A  ≠ Ø ) ∧ (X∩B  = Ø ) ) → (X∩ (A\B)  ≠  Ø )

 

6. Примеры эквивалентных преобразований

Первые два  примера  содержат доказательства свойств импликации из таблицы 1С (см. п.4).

Пример 1. Преобразуем выражение (¬y)→ (¬x в выражение x→ y.  Имеем:

1) (¬y)  (¬(¬x) )   - замена импликации дизъюнкцией

2)y)  x                - снятие двух отрицаний

3)   x  → y                   - замена дизъюнкции импликацией

Пример 2.  Преобразуем выражение  → (y→ z в выражение (xy)→ z.  Имеем:

1) ¬(xy) ∨ z                 - замена импликации дизъюнкцией

2) (x) ∨ (¬y) ) z    - правило де Моргана

3)  (¬x) ∨ ((¬y)  z )    - сочетательный закон для дизъюнкции

4)   (¬x (y  → z )   замена дизъюнкции импликацией

5)   x  → (y  → z )      замена дизъюнкции импликацией

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

Пример 3. Рассмотри выражение (x→ y)  z.  Имеем:

1) ((¬x)   y)  z  - замена импликации дизъюнкцией

2) (¬x)   (y  z)  - сочетательный закон для дизъюнкции

3) x   (y  z)  - замена дизъюнкции импликацией

Пример 4. Рассмотри выражение (x→ z  (y→ z).  Имеем:

1) ((¬x)   z)    ((¬y) ∨  z)   - две замены импликации дизъюнкцией

2) (¬x)   z    (¬y) ∨  z        - раскрытие скобок (сочетательный закон для дизъюнкции)

3) (¬x)    (¬y) ∨  z ∨  z        - переместительный закон для дизъюнкции

4) (¬x)    (¬y) ∨  z               - закон поглощения для дизъюнкции

5) ¬(x ∧ y) ∨                        - правило де Моргана

6) (x ∧ y)  →                         - замена дизъюнкции импликацией

 

 
 

1 Коммент

  1. [...] Обновлены материалы по логике с учетом новой А10. Теперь объяснение начинается с самого начала — с элементарных высказываний. Написано про связь логических операций с операциями нгад множествами. [...]

 
 

Что думаете?

 




 
 

 
 
Яндекс.Метрика