 |
|
Операции над высказываниями
Дизъюнкция высказываний (V, ИЛИ, OR). Дизъюнкция высказываний – высказывание, истинное тогда, когда истинно хотя бы одно из высказываний.
Конъюнкция высказываний (&, И, AND). Конъюнкцией высказываний называется высказывание, истинное тогда и только тогда, когда истинны все высказывания.
Отрицание высказываний (- над буквой, НЕ, NOT). Отрицанием высказывания называется высказывание, истинное только тогда, когда исходное высказывание ложно.
|A B |A & B A V B |Not A |
|Л Л |Л |Л |И |
|Л И |Л |И И |
|И Л |Л |И |Л |
|И И |И |И |Л |
Л – ложно.
И – истинно.
Утверждение (основа всей алгебры логики) Между множеством всех классов эквивалентных высказываний об элементах множества U и множеством P(U) можно установить взаимно однозначное соответствие, при котором операция дизъюнкции высказываний соответствует
операции объединения множеств истинности, а конъюнкция соответствует операции пересечения. Операция отрицания соответствует операции дополнения.
ТЕСТОВЫЕ ВОПРОСЫ К ТЕМЕ 3
1. Даны множества: А={3,5,7}и В={0,3,5,7,8}Найдите пересечение множеств А и В.
A){3,5,7};
B) {3,5};
C){0,8};
D){0,3,5,7,8};
E){7,8}.
2. Даны множества: А={4,6,8,10}и В={7,8,9,10,11}.Найдите объединение множеств А и В.
A) {7,8,9,10,11};
B) {4,6,8,10};
C){4,6,8,10,7,9,11};
D) {8,10};
E) {4,6,8,10,7,8,9,10,11}
3. Даны множества: А={1,2,3,4,5} и В={1,3,5}.Найдите множество .
A) {1,2,3,4,5};
B) {1,3,5};
C) {2,4};
D) {1,2,3,4,5,1,3,5};
E) {4,5}.
4. Логическое отрицание называется ...
A) импликация
B) дизъюнкция
С) эквивалентность
D) конъюнкция
E) инверсия
5. Логтческое умножения – это
A) дизъюнкция
B) импликация
C) инверсия
D) конъюнкция
E) эквивалентность
6.Логическое сложение соответствует союзу ...
A) тогда и только тогда, когда если …, то …
B) если …, то …
C) или
D) не
E) и
7. Логическое сложение называется ...
A) Эквивалентность
B) Инверсия
C) Импликация
D) Конъюнкция
E) Дизъюнкция
8. Логическое умножение обозначается ...
A) V
B) <->
C) ->
D) подчеркиванием сверху
E) ^, &
9. Логическое сложение обозначается ...
A) <->
B) ^, &
C) ->
D) V
E) подчеркиванием сверху
10. Логика - это ...
A) Наука о компьютерах
B) Наука о доказательствах
C) Наука о формах и способах мышления
D) Наука о способах моделирования
E) Наука о построении схем
Тема 4. Основы дискретной математики
Презентация-Основы логики и логические основы компьютера
Понятие графа
Слово «граф» в математике означает картинку, где нарисовано несколько точек, некоторые из которых соединены линиями. С дворянским титулом «граф» их связывает общее происхождение от латинского слова «графио» - пишу.
В математике определение графа дается так:
Графом называется конечное множество точек, некоторые из которых соединены линиями. Точки называются вершинами графа, а соединяющие линии – рёбрами.
Примерами графов могут служить схемы авиалиний, метро, дорог, электросхемы, чертежи многоугольников. Использует графы и дворянство. Например, в генеалогическом дереве, вершины – члены рода, а связывающие их отрезки – отношения родственности. Использует графы и дворянство. На рисунке приведена часть генеалогического дерева знаменитого дворянского рода. Здесь его вершины – члены этого рода, а связывающие их отрезки – отношения родственности, ведущие от родителей к детям.
Слово «дерево» в теории графов означает граф, в котором нет циклов, то есть в котором нельзя из некоторой вершины пройти по нескольким различным ребрам и вернуться в ту же вершину. Генеалогическое дерево будет деревом и в смысле теории графов, если в этом семействе не было браков между родственниками.
Деревья
Деревом называется любой связный граф, не имеющий циклов. Договорились считать «деревом» и всякий граф, состоящий из одной (изолированной) вершины.
Цикломназывается путь, в котором совпадают начало с концом.
Если все вершины цикла разные, то такой цикл называется элементарным(или простым) циклом. Если же цикл включает в себя все ребра графа по одному разу, то такой цикл называется Эйлеровой линией (рис.9а). В графе на рис.9б два цикла: 1-2-3-4-1 и 5-6-7-5.
Путемв графе от одной вершины к другой называется
такая последовательность ребер, по которой можно проложить маршрут между этими вершинами.
При этом никакое ребро маршрута не должно встречаться более одного раза. Вершина, от которой проложен маршрут, называется началом пути, вершина в конце маршрута — конец пути.
