29

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

Решение. Будем обозначать высказывания зрителей символом Х у, где X-

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

А2 Б5 ≡ 1, В2 Д3 ≡ 1, Г2 Б3 ≡ 1, А3 Е6 ≡ 1, В3 Е4 ≡ 1.

Но тогда будет истинной и формула

L ≡ (А2 Б5 )&(В2 Д3 )&(Г2 Б3 )&(А3 Е6 )&(В3 Е4 ).

Путем простых равносильных преобразований легко показать, что L ≡ А3&Б5&В2&Г1&Е4 . НоL ≡ 1и, значит,

А3 ≡ 1, Б5 ≡ 1, В2 ≡ 1, Г1 ≡ 1, Е4 ≡ 1, что и дает ответ на вопрос задачи.

Пример 7. Жили четыре мальчика: Альберт, Карл, Дидрих и Фридрих. Фамилии друзей те же, что и имена, только так, что ни у кого из них имя и фамилия не были одинаковы. Кроме того, фамилия Дидриха не была Альберт. Требуется определить фамилию каждого из мальчиков, если известно, что имя мальчика, у которого фамилия Фридрих, есть фамилия того мальчика, имя которого - фамилия Карла.

Решение. Поставим в соответствие каждому мальчику символ ΧΥ , где X-

имя, а Y - фамилия мальчика.

Тогда по условию задачи ложны высказывания:

АА, КK, ДД, ФФ, ДА,

но есть мальчик YХ такой, что истинна конъюнкция

ΧФ&YX &KY .

Очевидно, что Х≡Ф, Х≡К, Y≡Ф, Y≡К. Тогда возможны два случая:

1)Х≡А и Y≡Д.

2)Х≡ Д и Y≡А.

Но первый случай невозможен, так как здесь YХ≡ДА, а по условию ДА≡0. Следовательно, имеет место второй случай. Значит, Дидрих имеет

фамилию Фридрих, Альберт имеет фамилию Дидрих, Карл имеет фамилию Альберт, а Фридрих имеет фамилию Карл.

Пример 8. По подозрению в совершенном преступлении задержали Брауна, Джона и Смита. Один из них был уважаемым в городе стариком, другой был малоизвестным чиновником, третий - известным мошенником. В процессе следствия старик говорил правду, мошенник лгал, а третий задержанный в одном случае говорил правду, а в другом - ложь. Вот, что они утверждали:

Браун: «Я совершил это. Джон не виноват».

Джон: «Браун не виноват. Преступление совершил Смит». Смит: «Я не виноват, виновен Браун».

30

Определите имя старика, мошенника и чиновника и кто из них виноват, если известно, что преступник один.

Решение. Обозначим буквами Б,Д и С высказывания: виноват Браун, виноват Джон, виноват Смит соответственно. Тогда утверждения, высказанные задержанными ,можно записать в виде конъюнкций: Б& Д, Б&С, Б&С, из

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

L ≡ (Б& Д) (Б&С) (Б&С).

Таблица истинности этой формулы имеет вид:

Отсюда видно, что формула Lистинна в пяти из восьми занумерованных случаев. Случай 4 следует исключить из рассмотрения, так как здесь оказываются истинными две конъюнкции, а это противоречит условию задачи. В случаях 2, 3 и 5 оказываются истинными по два высказывания: Б и Д, Б и С, Д и С соответственно, что также противоречит условию задачи.

Следовательно, справедлив случай 7, то есть преступник - Смит. Он - известный мошенник, и оба его высказывания ложны: Б&С ≡ 0 . При этом высказывания Б и Д ложны. Значит, истинна пара высказываний Джона, а у Брауна первое высказывание ложно, а второе истинно. Отсюда ясно, что Джон - уважаемый в городе старик, а Браун -малоизвестный чиновник.

1.14 Алгебраические структуры на множествах

Под алгебраической структурой на множестве мы будем понимать множество, снабженное операцией или операциями над элементами множества. Свойства этих операций оговариваются в аксиомах. По количеству операций и набору аксиом различают следующие алгебраические структуры. Итак, алгебраическая структура есть система (Χ, f1, f2, … fn),

где Χ – множество, f1, f2, … fn – операции над элементами Χ.

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

1)любой паре элементов q1, q2 G ставится в соответствие однозначно определенный элемент q1 ○ q2 G.

31

2)для любых трех элементов q1, q2 , q3 G имеем: q1 ○ (q2 ○ q3 ) = (q1 ○ q2 ) ○ q3

3)единичный элемент такой, что е G:

е ○ q = q ○ е = q q G

4) q G существует обратный элемент q -1 G / q –1 ○ q = q ○ q –1 = е

Замечание 1. Если в алгебраической структуре помимо операции умножения имеются и др. операции, то в аксиомах 3 и 4 иногда добавляют: относительно операции умножения.

Замечание 2. Алгебраическую структуру <G, ○> с аксиомами 1, 2 называют полугруппой, а с аксиомами 1, 2, 3 – моноидом.

Группа называется коммутативной (абелевой), если вместе с аксиомами 1 – 4 выполняется следующая аксиома: 5) q1 ○ q2 = q2 ○ q1 q1, q2 G.

Пример 9. Множество целых чисел: <Z, +> (Z – множество целых чисел, + - операция сложения) являются группой. Роль единичного элемента по сложению играет 0, а обратного элемента – противоположный. Эта группа является коммутативной.

Пример 10. Алгебраическая структура <Z, ○>, где Z – множество целых чисел, ○ - операция умножения, не образует группу, так как элемент 0 не имеет обратного. Эта алгебраическая структура является моноидом.

Пример 11. Множество матриц второго порядка с ≠ 0 определителем образует группу. Эта группа не является коммутативной.

Определение. Алгебраическая структура (R, *, ○) называется кольцом, если выполняются следующие аксиомы:

1) (R, *) – коммутативная группа; 2) (R, ○) – полугруппа; 3) выполняются распределительные законы.

Если операция ○ коммутативна, то кольцо называется коммутативным (абелевым). Если в кольце существует единица относительно ○, то кольцо называется кольцом с единицей.

Пример 12. (Z, *, ○) – коммутативное кольцо с единицей.

Пример 13. Множество квадратных матриц второго порядка (операции сложения и умножения) являются некоммутативным кольцом с единицей. Определение. Кольцо (R, *, ○) называется полем, если любой ненулевой

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

Пример 14. Множество действительных чисел <R, *, ○> является полем. Существуют и более сложные алгебраические структуры, в которых для образования элементов привлекаются элементы других стандартных

множеств.

32

ГЛАВА 2 ЛИНЕЙНАЯ АЛГЕБРА

2.1 Понятие о матрице, виды матриц

Определение. Матрицей называется прямоугольная таблица чисел вида:

Числа a11, a12 , amn , составляющие матрицу, называются ее элементами. В обозначении элемента aij (i = 1,2, ,m; j = 1,2, ,n) матрицы А

индекс i означает номер строки, а индекс j – номер столбца, на пересечении которых находится этот элемент.

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

имеющую размеры n × n.

Ясно, что квадратная матрица порядка n имеет n2 элементов. Определение. Матрица A, имеющая размеры 1×n, называется матрицей-

Матрица, состоящая из одного элемента, отождествляется с этим эле-

ментом, т.е. (a11) = a11.

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

Определение. Квадратная матрица n-го порядка, у которой главная

диагональ a :i = j состоит из единиц, а все остальные элементы равны

ij

33

2.2Определители n -го порядка. Минор и алгебраическое дополнение

Одной из важнейших характеристик квадратной матрицы A порядка n является ее определитель или детерминант, который обозначается |A| или detA. Определитель матрицы - это число, сопоставляемое матрице по описываемым ниже правилам.

Понятие определителя вводится индуктивно.

Определение. Определителем (или детерминантом) |A| матрицы A первого порядка называется единственный элемент, из которого эта матрица состоит, т.е. для A=(a11)

Определение. Алгебраическим дополнением элемента aij называется его

минор Mij, взятый со знаком (-1)i+j, т.е. Aij = (-1)i+j · Mij.

Например, A11 = (-1)1+1 · M11, A21 = (-1)2+1 · M21 и т.д.

34

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

Формулы (2.7), (2.8) дают разложение определителя по элементам первой строки.

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

n

по любой строке и по любому столбцу, т.е.

A = aij Aij , (разложение определителя n-го порядка по i-ой строке) j=1

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

Замечание. Определитель 3-го порядка можно вычислить способом треугольника, который заключается в следующем: элементы a11, a22, a33 составляют главную диагональ определителя, элементы a13, a22, a31 – побочную диагональ. Тогда определитель 3-го порядка равен сумме произведений элементов, стоящих на главной диагонали и стоящих в вершинах треугольников, одна сторона которых параллельна главной диагонали, минус произведения элементов, составляющих побочную диагональ и стоящих в вершинах треугольников со стороной, параллельной побочной диагонали.

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

6.Если все элементы какой-либо строки (столбца) определителя представлены в виде суммы двух слагаемых, то определитель равен сумме двух

определителей:

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

2.4 Операции над матрицами. Линейные операции

Определение. Две матрицы A = (aij) и B = (bij) называются равными, если они имеют одинаковые размеры и их соответствующие элемен-

ты равны, т.е. aij = bij (i = 1, 2, …, m, j = 1, 2, …, n).

К линейным операциям над матрицами относятся операции сложения матриц и умножения матрицы на число (скаляр).

Пусть матрицы A = (aij) и B = (bij) - две матрицы размера m × n. Определение. Суммой матриц A и B называется матрица C = A + B разме-

ра m × n, каждый элемент которой есть сумма соответствующих элементов слагаемых.

размер которой 3 × 2.