Как сдать экзамен по дискретной математике

documentclass[a4paper]{article}

usepackage[utf8]{inputenc}
usepackage{amsthm,amsmath,amsfonts, amssymb}
usepackage[english,russian]{babel}

usepackage{concrete}
usepackage{enumerate}
usepackage{euler}
usepackage{fullpage}

pagestyle{empty}
selectlanguage{russian}

begin{document}

selectlanguage{russian}

%1%

end{document}

Дискретная математика hfill %1%

весна $2013$ hfill группа %2%

section*{Домашнее задание}

begin{enumerate}
item Для формулы пропозициональной логики
$$ varphi = %3%: $$
begin{enumerate}[(i)]
	item постройте таблицу истинности;
	item переведите $varphi$ в совершенную конъюнктивную и совершенную дизъюнктивную нормальные формы;
	item выразите $varphi$ в виде полинома Жегалкина;
	item $[ast]$ выразите $varphi$ при помощи штриха Шеффера $xmid y = lnot(xland y)$.
end{enumerate}

pagebreak

class Globals {
public:
    size_t TypesNo;
    size_t VarType;
    vector<string> TypesLatex;
    vector<size_t> TypesArity;
    boost::random::uniform_int_distribution<> RandomNodeType;
    boost::random::uniform_int_distribution<> RandomNodeNoVar;
    boost::random::uniform_int_distribution<> RandomNodeBinary;

    size_t VarsNo;
    vector<string> VarNames;
    boost::random::uniform_int_distribution<> RandomVarType;
    size_t current_varnum;

    Globals(size_t types_num, vector<string> types_latex, vector<size_t> types_arity, size_t var_num, vector<string> var_names) :
        TypesNo(types_num), VarType(types_num - 1), TypesLatex(types_latex), TypesArity(types_arity),
        RandomNodeType(0, types_num - 1), RandomNodeNoVar(0, types_num - 2), RandomNodeBinary(0, types_num - 3),
        VarsNo(var_num), VarNames(var_names), RandomVarType(0, var_num - 1), current_varnum(var_num - 1) {}

    size_t get_next_var() {
        current_varnum++;
        if (current_varnum == VarsNo) current_varnum = 0;
        return current_varnum;
    }
};

Globals GBoolean(7,
				{ "\land", "\lor", "\rightarrow", "\oplus", "\equiv", "\lnot", "\var" },
				{ 2, 2, 2, 2, 2, 1, 0 },
				4,
				{ "x", "y", "z", "t" });

Globals GSet(5,
			{ "\cap", "\cup", "\triangle", "\overline", "\var" },
			{ 2, 2, 2, 1, 0 },
			3,
			{ "A", "B", "C" });

class BNode {
public:
    Globals *glob;
    size_t type;
    size_t varnum;
    BNode * left;
    BNode * right;

    BNode(Globals *g, size_t t, bool must_be_leaf = false, bool must_not_be_leaf = false, bool must_be_binary = false) : glob(g), type(t), left(NULL), right(NULL) {
        if (t == g->TypesNo) { // this means we want a random node
            type = must_be_leaf ? g->VarType
                : (must_be_binary ? g->RandomNodeBinary(gen)
                    : (must_not_be_leaf ? g->RandomNodeNoVar(gen)
                        : g->RandomNodeType(gen) ));
        }
        varnum = (type == g->VarType) ? g->get_next_var() : 0;
    }

    ~BNode() {
        if (left != NULL) delete left;
        if (right != NULL) delete right;
    }
};

    string TypeString() const {
        if (type == glob->VarType) return glob->VarNames[varnum];
        return glob->TypesLatex[type];
    }

    string ToString() const {
        if (glob->TypesArity[type] == 0) return TypeString();
        if (glob->TypesArity[type] == 1) return TypeString() + "{" + left->ToString() + "}";
        return "(" + left->ToString() + " " + TypeString() + " " + right->ToString() + ")";
    }

    bool get_truth_value(const vector<bool> & vals) {
        switch(type) {
            case 0: return left->get_truth_value(vals) && right->get_truth_value(vals); break;
            case 1: return left->get_truth_value(vals) || right->get_truth_value(vals); break;
            case 2: return (!left->get_truth_value(vals)) || right->get_truth_value(vals); break;
            case 3: return left->get_truth_value(vals) != right->get_truth_value(vals); break;
            case 4: return left->get_truth_value(vals) == right->get_truth_value(vals); break;
            case 5: return !left->get_truth_value(vals); break;
            case 6: return vals[varnum]; break;
            default: return false; break;
        }
    }

BNode *generate_tree(Globals & g, size_t min_depth, size_t max_depth, bool must_be_binary = false) {
    if (max_depth == 0) return NULL;
    BNode *node = new BNode(&g, g.TypesNo, max_depth == 1, min_depth > 0, must_be_binary);
    if (g.TypesArity[node->type] == 1) {
        node->left = generate_tree(g, min_depth, max_depth, true);
    }
    if (g.TypesArity[node->type] == 2) {
        node->left = generate_tree(g, min_depth - 1, max_depth - 1);
        node->right = generate_tree(g, min_depth - 1, max_depth - 1);
    }
    return node;
}

void process_one_student_file_boolean(string dir, string fname,
        boost::format & general_tmpl, boost::format & problem_tmpl, boost::format & solution_tmpl) {
    BNode *node_bool;

    ostringstream s;
    vector<string> students = readAllLinesFromFile(dir + "/" + fname + ".txt");
    cout << "tГруппа " << fname << endl;
    for (size_t i=0; i<students.size(); ++i) {
        if (students[i].size() == 0) continue; // empty line
        cout << "tt[ " << students[i] << " ]" << endl;
        node_bool = generate_tree(GBoolean, 2, 4);
        string group_string = "$" + fname + "$";
        s << problem_tmpl % students[i] % group_string
                          % node_bool->ToString();
        delete node_bool;
    }
    ofstream ofs(dir + "/" + fname + ".tex");
    ofs << general_tmpl % s.str() << endl;
    ofs.close();
}

string students_dir = "2013";
vector<string> students_files = { "BoTR" };

int main(int argc, char *argv[]) {
    boost::format boolean_tpml( read_file_as_string("boolean_problem_minimal.tex") );
    boost::format general_tmpl( read_file_as_string("general_template.tex") );

    for (size_t i = 0; i < students_files.size(); ++i) {
        process_one_student_file_boolean(students_dir, students_files[i], general_tmpl, boolean_tpml);
    }

    return 0;
}

    void depth_first(function<void (const BNode * n)> do_with_node) {
        do_with_node(this);
        if (left != NULL) left->depth_first(do_with_node);
        if (right != NULL) right->depth_first(do_with_node);
    }

bool sanity_check(BNode * node) {
    vector<bool> vars_present(node->glob->VarsNo, false);
    vector<bool> connectors_present(node->glob->TypesNo, false);
    node->depth_first([&] (const BNode * n) {
        if (n->type == n->glob->VarType) {
            vars_present[ n->varnum ] = true;
        } else {
            connectors_present[ n->type ] = true;
        }
    });
    return all_of( vars_present.begin(), vars_present.end(), [](bool b) {return b;} ) &&
           (accumulate(connectors_present.begin(), connectors_present.end(), 0) > 2);
}

{footnotesize
subsection*{%1%, группа %2%}

Таблица истинности для формулы $%3%$:
$$ %4% $$

}
pagebreak 

    bool increment_counter(vector<bool> & v) {
        for (int i=v.size()-1; i>=0; --i) {
            if (!v[i]) {
                v[i] = true;
                for (size_t j=i+1; j<v.size(); ++j) v[j] = false;
                return true;
            }
        }
        return false;
    }

    string latex_truthtable() {
        ostringstream os;
        vector<bool> counter(glob->VarsNo, false);
        os << "\begin{array}{";
        for(size_t i=0; i<counter.size(); ++i) os << 'c';
        os << "|c}n";
        for(size_t i=0; i<counter.size(); ++i) os << glob->VarNames[i] << " & ";
        os << " \\\hlinen";
        do {
            for(size_t i=0; i<counter.size(); ++i) os << counter[i] << " & ";
            os << get_truth_value(counter) << "\\n";
        } while (increment_counter(counter));
        os << "\end{array}n";
        return os.str();
    }

void process_one_student_file_boolean(string dir, string fname,
        boost::format & general_tmpl, boost::format & problem_tmpl, boost::format & solution_tmpl) {
    BNode *node_bool;

    ostringstream s, ssolution;
    vector<string> students = readAllLinesFromFile(dir + "/" + fname + ".txt");
    cout << "tГруппа " << fname << endl;
    for (size_t i=0; i<students.size(); ++i) {
        if (students[i].size() == 0) continue; // empty line
        cout << "tt[ " << students[i] << " ]" << endl;
        do {
            node_bool = generate_tree(GBoolean, 2, 4);
        } while (!sanity_check(node_bool));
        string group_string = "$" + fname + "$";
        s << problem_tmpl % students[i] % group_string
                          % node_bool->ToString();
        ssolution << solution_tmpl % students[i] % group_string
                          % node_bool->ToString() % node_bool->latex_truthtable();
        delete node_bool;
    }
    ofstream ofs;
    open_for_writing(dir + "/" + fname + ".tex", ofs);
    ofs << general_tmpl % s.str() << endl;
    ofs.close();
    
    open_for_writing(dir + "/" + fname + ".sol.tex", ofs);
    ofs << general_tmpl % ssolution.str() << endl;
    ofs.close();
}

string students_dir = "2013";
vector<string> students_files = { "BoTR" };

int main(int argc, char *argv[]) {
    boost::format boolean_tpml( read_file_as_string("boolean_problem_minimal.tex") );
    boost::format solution_tpml( read_file_as_string("boolean_solution_minimal.tex") );
    boost::format general_tmpl( read_file_as_string("general_template.tex") );

    for (size_t i = 0; i < students_files.size(); ++i) {
        process_one_student_file_boolean(students_dir, students_files[i], general_tmpl, boolean_tpml, solution_tpml);
    }

    return 0;
}

Tony

Абитуриент

• 

• Пользователи

• 

• 10 сообщений

Народ, подскажите плиз что творится на экзамене по ДМ?
2 курс. :blink:

Антошка

• Район:Россия, Москва, Ясенево

Твое спасение — Митин (если он будет) Я Сироте сдавал, если все знаешь более-менее, то 4 получишь. А засранец Губанов часа полтора всех на троечку драл, сцуко. Там сначала на 3 белет решаешь, если все правильно, то посишь задание на 4, мне надо было Т триггер сваять+таблицы истинности к нему. Если 5 захочешь — еще задание проси. Если задание не сделаешь, то и 3 не получишь, я если б это знал, на 3 бы остановился, хотя так 4 получил =)

Tony

Абитуриент

• 

• Пользователи

• 

• 10 сообщений

препод у нас Гусева. а что именно там в билетах ваще? какие темы?

Антошка

• Район:Россия, Москва, Ясенево

Да я уже не помню толком. Декомпозиция автоматов точно будет

Tony

Абитуриент

• 

• Пользователи

• 

• 10 сообщений

хм =) какая нафик декомпозиция автоматов !? =) у нас дискретка тока первый семестр идёт.

Антошка

• Район:Россия, Москва, Ясенево

Ну тогда совсем не помню, в первом семестре я еле-еле, че-то как-то, раком-боком 3 получил и был счастлив

zapadlo

Абитуриент

• 
• Пользователи

• 

• 3 сообщений

Если надо то вот шпоры http://webfile.ru/744136 :thumb:

le_shka

• Пол:Мужчина
• Район:город-герой Москва

Круто! Реальные шпоры! :thumb:

antilopka

• Район:Мосрентген

ага тока они по первому семестру:(

SYNED

• Пол:Мужчина
• Район:Квартирка на Пятницкой

на экзаме все к Сироте друзья и братья!

antilopka

• Район:Мосрентген

Губаныч у нас семинары вел, нашу группу он валить не будет, наоборот:) особенно любимчиков:)

а я Митину все сдал:) его очень легко было уговорить на 4. так что это халява, а также вся сессия халявная

MrFreeMan.DNA

• Район:Из глубин квазиподпространства.

а я Митину все сдал:) его очень легко было уговорить на 4. так что это халява, а также вся сессия халявная

<{POST_SNAPBACK}>

Не говори,
что не сдал — то тебе сам деканат задвигает, как с ТОЭ сделали )))

А ты читер, сироте ты бы выше чем на три ни в жизни не сдал.

-.::MaZaFaKa::.-

• Район:Moscow-City

а Губанову и на 3 сдать ОЧЧЧень сложно…. он реально как автомат работает…. или 3 или 2… больше никто не получил, вроде…

Губанов — автомат, у которого на выходе получается либо ждите, либо 2, либо 3. Причем 3 он выдает только после 20 «ждите»

Falling Star

• Район:Inferno

Элементарный предмет+)
Митин, Сирота — самые классные преподы.

Сироте ты нифига не сдашь, проверено уже не раз

MrFreeMan.DNA

• Район:Из глубин квазиподпространства.

Сироте ты нифига не сдашь, проверено уже не раз

<{POST_SNAPBACK}>

а вот нифига, он не валит, но и халяву не ставит.

Решил три задачи — получай тройку.
решил 2 — иди на йух.

и так далее.

Infidel

Абитуриент

• 

• Пользователи

• 

• 22 сообщений

• Район:Щёлково

Губанов — автомат, у которого на выходе получается либо ждите, либо 2, либо 3. Причем 3 он выдает только после 20 «ждите»

<{POST_SNAPBACK}>

Сдал Губанову на 4 практически без проблем, если не считать того что, когда он меня увидел, то сразу захотел влепить пару(за сем я с ним ни раз дескутировал по разным поводам( *_* ) )
Так что даже если он испытывает к тебе личную «нелюбовь» , сдать реально даже на 4.

Пулькин рулит однозначно, хотя экзамен я ему не сдавал, но за ааабсолютно несуществующую курсовую поставить 3 может только он))

ПРЕДИСЛОВИЕ

Дискретная математика – одна из важнейших составляющих современной математики. В отличие от других математических дисциплин учебного плана направления бакалавриата «Бизнес-информатика», таких как математический анализ, линейная алгебра и др., дискретная математика имеет дело с объектами нечисловой природы, что позволяет, в частности, использовать ее методы для моделирования социальных и экономических процессов. Понятия и методы дискретной математики необходимы для постановки различных прикладных задач, для усвоения и разработки современных информационных технологий, лежат в основе теории и практики программирования.

Целью изучения дисциплины «Дискретная математика» является освоение соответствующего математического аппарата, позволяющего анализировать, моделировать и решать прикладные (в том числе экономические) задачи.

Задачи изучения вытекают из требований к результатам освоения программы бакалавриата компетенций, установленных Федеральным государственным образовательным стандартом высшего профессионального образования (ФГОС-3+) по направлению 38.03.05 «Бизнес-информатика».

Входе изучения дисциплины ставятся задачи:

‒освоение методов дискретной математики для решения прикладных

задач;

‒выработка умения моделировать реальные объекты и процессы с использованием математического аппарата дискретной математики;

‒развитие логического и алгоритмического мышления студентов, повышение уровня их математической культуры;

‒развитие навыков самостоятельной работы по изучению учебной и научной литературы.

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

Всоответствии с ФГОС-3+ по направлению «Бизнес-информатика». квалификация академический бакалавр, процесс изучения дисциплины «Дискретная математика» на формирование следующих компетенций:

общекультурных компетенций (ОК)

– способность к самоорганизации и самообразованию (ОК-7);

профессиональных компетенций (ПК)

– способность использовать основные методы естественнонаучных дисциплин в профессиональной деятельности для теоретического и экспериментального исследования (ПК-17);

–способность использовать соответствующий математический аппарат

иинструментальные средства для обработки, анализа и систематизации информации по теме исследования (ПК-18);

–умение готовить научно-технические отчеты, презентации, научные публикации по результатам выполненных исследований (ПК-19).

Врезультате изучения дисциплины студент должен:

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

б) уметь:

–применять методы дискретной математики для решения прикладных

задач;

–строить математические модели прикладных задач.

в) владеть навыками решения задач дискретной математики.

По дисциплине ««Дискретная математика» студенты бакалавриата направления «Бизнес-информатика» должны выполнить одну контрольную работу (задания к которым приводятся в данном пособии). Контрольная работа (в соответствии с учебным графиком) могут быть существенно дополнена за счет частичного использования компьютерной обучающей программы (КОПР). В процессе изучения дисциплины студенты проходят компьютерное тестирование и сдают экзамен.

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

.

Содержание дисциплины и

методические рекомендации по ее изучению

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

Контрольные вопросы по каждой теме представлены ниже в разделе «Вопросы для самопроверки».

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

Вопросы выполнения контрольных работ с частичным использованием КОПР рассматриваются в брошюре [Электронные ресурсы, 3]: «Математика. Методические указания по проведению и выполнению контрольных работ с использованием КОПР».

Тема 1. Множества, функции, отношения

Множества – основные понятия. Диаграммы Венна. Операции над множествами: объединение, пересечение, дополнение. Кортежи и прямое (декартово) произведение множеств. Соответствия и их свойства. Взаимно однозначные соответствия. Мощности бесконечных множеств. Принципы включений – выключений. Понятие функции. Обратные функции. Суперпозиции и формулы. Способы задания функций. Общее понятие отношения. Бинарные отношения и их свойства (рефлексивность, симметричность, транзитивность). Отношение эквивалентности и классы эквивалентности. Отношение порядка. Линейный порядок и частичный порядок. ([1, часть 2, кроме § 5, 6]; [2, разд. 1.1‒ 1.3]; [3, § 5.1, 13.1 – 13.3]).

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

подмножества В (части данного множества А: В А ), пустого множества

(не содержащего ни одного элемента), дополнения А множества А (состоящего из всех элементов некоторого универсального множества2 U, не входящих в множество А). Определялись основные операции над множествами А и В: объединение А В (множество, состоящее из всех элементов множества А и В), пересечение А В (множество, состоящее из всех общих элементов А и В), разность А В (множество, состоящее из всех элементов множества А, не входящих в множество В).

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

2Под универсальным множеством здесь понимается множество, включающее все множества, участвующие в рассматриваемой задаче.

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

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

Если между множествами А и В имеет место взаимно однозначное

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

состоят из одинаковых элементов), не эквивалентные (так как имеют разные мощности (число элементов)), причем множество Е включается в множество

D ( E D ). ►

Бинарным (двухместным) отношением множеств А и В называется

рефлексивность, симметричность, транзитивность ([1, часть 2, § 10]; [3, §13.3]). Бинарное отношение, для которого выполнены указанные три свойства, называется отношением эквивалентности, являющееся обобщением понятия равенства. Подмножества элементов, эквивалентные данному, называется его классом эквивалентности. Если бинарное

3 Множество называется счетным, если оно эквивалентно множеству натуральных чисел (его элементы можно перенумеровать).

и обществознанию: А С

Следовательно, только одну тройку по математике имеют 86–

–9–6–18=53 (чел).

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

71– (27–18) –(27–18) –18=35 (чел)

и по обществознанию:50–(24–

–18) – (27–18) –18=17 (чел). Всего абитуриентов, имеющих только одну тройку, равно 53+35+17=105

(чел). Решение задачи легко иллюРис. 1 стрируется на диаграмме Венна.

(рис.1)►

Тема 2. Комбинаторика

Предмет комбинаторики. Правило суммы и правило произведения. Размещения, перестановки, сочетания без повторений и с повторениями. Биномиальные коэффициенты и соотношения для них. Задачи перечисления. Подсчет числа функций с конечными областями определения. ([1, часть 3]; [2, разд. 3.1]); [3, § 1.5]).

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

Студенты должны четко знать правила комбинаторики:

— правило суммы: если объект А1 может быть выбран n1 способами, А2 –

осуществлен n1 n2 способами.

Из множества n различных элементов могут быть образованы подмножества (комбинации) из m элементов 0 m n.

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

(где n! 12 3 …n ).

Если комбинации из n элементов по m отличаются только составом элементов, то их называют сочетаниями. Число сочетаний из n элементов по m находятся по формуле:

элементов, то их называют перестановками. Число перестановок из n элементов находится по формуле:

Pn n!

Пример 3. В первом туре конкурса участвуют 16 человек. Сколько существует различных исходов этого тура, при которых совпадают участники, занявшие призовые 1-е, 2-е и 3-е места, а также два участника, занявшие 15-е и 16-е места и выбывающие из дальнейшего участия в конкурсе?

Р е ш е н и е. Способы распределения участников, занявших 1-е, 2-е и 3-е места (из 16), отличаются как составом участников, так и их порядком; их число – число размещений А163 . Из оставшихся 16 3 13 участников два

выбывают из конкурса (порядок этих участников значения не имеет); их число – число сочетаний С132 . По правилу произведения (см. с. получаем,

что число различных исходов первого тура конкурса, удовлетворяющих условию задачи, есть

Другой способ решения состоит в том, что общее число различных исходов первого тура с 16-ю участниками (без учета распределения тех или иных мест) равно числу перестановок P16 . Перестановки участников,

занявших места с 4-го по 14-е (т.е. 11 мест), а также 15-е и 16-е места (2 места) приводят к совпадающему в соответствии с условием исходу первого тура; их число (по правилу произведения) равно P11 Р2 . Значит, число различных исходов первого тура конкурса, удовлетворяющих условию, есть

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

Соответствующие формулы таких комбинаций с повторениями, приведены в пособии ([1, часть 3]; [3, § 1.5]). Там же рассматриваются задачи на подсчет различных комбинаций [1, 1-ое практическое занятие]; [3, примеры 1.11 – 1.15].

Тема 3. Математическая логика

Основные понятия логики: высказывания и рассуждения. Основные логические операции и их свойства. Алгебра высказываний. Понятие о булевской алгебре; алгебра высказываний как интерпретация булевской алгебры. Логические функции и способы их задания – таблицы и формулы. Дизъюнктивные и конъюнктивные формы. Теорема о функциональной полноте. Исчисление высказываний. Понятие об алфавите, формулах, аксиомах, правилах вывода и основных теоремах исчисления высказываний. Логика предикатов. Предметная область и предметные переменные. Кванторы общности и существования. Свободные и связанные переменные. Эквивалентные соотношения в логике предикатов. Общезначимые и противоречивые формулы. Запись утверждений естественного языка в логике предикатов. Понятие об исчислении предикатов ([1, часть 1, кроме §

11]; [2, разд. 1.4,1.5]; [3, § 13.1 – 13.3]).

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

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

Надо четко знать основные логические операции: отрицание высказывания Х (высказывание Х , которое истинно, когда Х ложно, и ложно, когда Х – истинно), конъюнкция (дизъюнкция) двух высказываний Х и Y

Логические операции высказываний тесно связаны с операциями над множествами. Отрицание высказывания соответствует дополнению