4 Построение отрицания

Р(х) определяется на А

(равносильность понимается в том случае, если слева стоит истинное высказывание, то справа – истина, слева – ложь, то и справа - ложь).

Доказательство:

1)

2)

ПРАКТИКА «

2. Нахождение формул по таблице истинности ( ) – новое высказывание, которое И, когда оба высказывания И.

A	B	C	f
И И И Л Л Л Л	И И Л И Л Л И	И Л Л Л И Л И	И Л И Л И Л И

3. Имеется комитет из 3 человек. Решении применяемым нажатием кнопки и простым большинством.

Если за – И, против Л. Составить формулу работы комитета.

A	B	C	f
И И И И Л Л Л Л	Л Л И И Л И Л И	И Л И Л Л И И Л	И Л И И Л И Л Л

4. Завуч составляя расписание на понедельник в 6 классе и стремится выполнить просьбу учителей: математики (1, 2, 3), физики (1, 3, 4), русского языка (2, 3), географии (1, 4). Сколькими способами?

Пусть:

5 способов, все это возможно.

Лекция 5 ПЕРЕСТАНОВКИ. ТРАНСПОЗИЦИЯ. БЕСПОРЯДОК ИЛИ ИНВЕРСИЯ. ОПРЕДЕЛИТЕЛЬ N-ГО ПОРЯДКА.

Пусть дано А, содержащее n различных элементов.

Будем образовывать из элементов множества А упорядоченное множество.

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

Определение: Всякое расположение элементов множества в определенном порядке, называют перестановкой элементов этого множества.

Вычислим, сколько упорядоченных множеств можно образовать из n – элементного множества.

Любое упорядоченное множество из А можно записать в следующем виде:

, где

-один из элементов

- можно выбрать n способов

- можно выбрать (n-1) способов

- 1 способ

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

Теорема: Число перестановок n – элементов множества А равно n факториал.

Замечание: Договор:

ТРАНСПОЗИЦИЯ

Если в заданной перестановке поменять местами какие-либо два элемента, а все остальные оставить на своих местах, то получится новая перестановка.

Такое преобразование перестановок называют транспозицией.

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

БЕСПОРЯДОК ИЛИ ИНВЕРСИЯ

Рассмотрим . Пусть , по перестановке оно стоит левее. В этом случае говорят, что образуют беспорядок или инверсию.

Пример: 4, 2, 3, 1 - 5 инв

Определение: Если перестановка содержит четное число инверсий, то она называется четной.

Теорема: При совершении одной транспозиции, четность перестановки меняется.

Доказательство:

I Переставляемые числа находятся рядом

Возьмем какой-нибудь элемент из В, например

- все инверсии с сохраняются при

- все инверсии внутри – сохран.

- все инверсии внутри – сохран.

- все инверсии с - сохран.

- все инверсии с - сохран.

Аналогично все инверсии чисел из С при сохраняются.

Пусть (*) содержит t инверсий,

(**) содержит S инверсий

1) Если , то при на 1 инверсию стало меньше

2) , то при на 1 инверсию стало больше

Можно записать

не могут быть одной четностью, действительно пусть - четные

II Переставляемые числа не стоят рядом.

(*)

(**)

(…)

К этому моменту совершили m транспозиций.

Сделаем еще одну транспозицию

(….)

Совершим m-транспозицию

Всего сделали (2m+1) транспозиций рядом стоящих чисел.

Так как мы меняли четность (2m+1) раз – нечетное число раз, то (*) и (**) раз чисел.

ОПРЕДЕЛИТЕЛЬ N-ГО ПОРЯДКА

Определение 1:

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

Определение 2:

Аналогично вычитаем третьего порядка, только каждый член содержит 3 многочлена.

Определение 3: Пусть дана матрица n-го порядка.

Определителем n-го порядка А называется сумма всевозможных членов, представляющих собой произведение n элементов матрицы А, взятых по одному и только по одному из каждой строки и каждого столбца, причем знак этого члена совпадает со знаком , где t – число инверсии в перестановке вторых номеров, при условии, что первые номера располагаются по порядку.

сумма всевозможных членов

Среди чисел нет ни одной пары одинаковых.

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

- членов будет столько, сколько перестановок

Теорема о знаке члена определителя.

Пусть (1) - член n-го порядка, тогда знак этого члена совпадает со знаком , где

S – число инверсий в перестановке первых номеров

t – число инверсий в перестановке вторых номеров.

(2) - число инверсий

(3) - число инверсий

Для того, чтобы узнать знак члена (1), надо переставить сомножители так, чтобы первые номера шли в порядке .

В (1) перестановим какие-нибудь два сомножителя. (например, 1 и 2)

(4)

(5) - инверсия

- инверсия

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

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

Рассмотрим (5), (5) получена из (2) 1 транспозиции, значит четность перестановки меняется разной четности, разной четности.

При вычитании разной четности получается число нечетное.

одинаковой четности

Перестановим сомножители в (1) так, чтобы номера первые или по порядку. Пусть при этом мы совершили перестановку сомножителей, при этом получим:

перестановка первых номеров

перестановка вторых номеров

Пусть - число инверсий первых номеров,

- число инверсий вторых номеров

(7)

Итак, (8) первые номера по порядку

(9) инверсий

Мы доказали .

Итак, по определению это и есть знак члена .