Your feedback will help us make our courses better, and we use your feedback each time we make updates to our courses. If you come across any urgent problems, email contact saylor. Your grade for the exam will be calculated as soon as you complete it. If you do not pass the exam on your first try, you can take it again as many times as you want, with a 7-day waiting period between each attempt. Once you pass this final exam, you will be awarded a free Course Completion Certificate.
Skip to main content. Side panel. Log in or Sign up. Log in or Sign up to track your course progress, gain access to final exams, and get a free certificate of completion! Course Introduction Time: hours. Free Certificate. Course Syllabus Page.
2. Truth values as logical values
Completing this unit should take you approximately 10 hours. Unit 3: Introduction to Number Theory This unit is primarily concerned with the set of natural numbers. Completing this unit should take you approximately 32 hours. Unit 4: Rational Numbers In this unit, you will learn to prove some basic properties of rational numbers. Completing this unit should take you approximately 9 hours. Unit 5: Mathematical Induction In this unit, you will prove propositions about an infinite set of positive integers.
Completing this unit should take you approximately 4 hours. Unit 6: Relations and Functions In this unit, you will learn about binary relations from a set to a set. Completing this unit should take you approximately 8 hours. Unit 8: Combinatorics In this unit, you will learn to count.
Completing this unit should take you approximately 11 hours. Course Feedback Survey Please take a few minutes to give us feedback about this course. Getting Started. Discussion Forums. MA Introduction to Mathematical Reasoning. Course Introduction. Unit 1: Logic. Unit 2: Sets. Unit 3: Introduction to Number Theory. Unit 4: Rational Numbers. Unit 5: Mathematical Induction. Unit 6: Relations and Functions. A hypothesis of a formula is said to be simple if it is a conjunction of variable formulas or their negations and if, after discarding any one of its factors, it is no longer a hypothesis of the formula.
Similarly, a consequence of is called simple if it is a disjunction of variable formulas or their negations and if, after one of its elements is discarded, it is no longer a consequence of. The survey of hypotheses and consequences is based on the indication of an algorithm which transforms a given formula into all of its simple hypotheses and consequences and, with the aid of the laws 2 — 7 , into all remaining hypotheses and consequences. The algorithm is based on the following facts. If , then and have identical hypotheses and identical consequences.
An element of a disjunctive normal form is a hypothesis of that disjunctive normal form, while a factor of a conjunctive normal form is a consequence of that conjunctive normal form. If is a hypothesis of a proposition , then is also a hypothesis for ; if is a consequence of , then is also a consequence of. If and are hypotheses of a proposition , then is also a hypothesis for ; if and are consequences of , then is also a consequence of.
A perfect disjunctive normal form has no hypotheses not containing letters which are not contained in that disjunctive normal form other than the disjunctions of some of its elements or of disjunctive normal forms equal to them. A perfect conjunctive normal form has no consequences other than the conjunctions of some of its factors or of propositions equal to them.
A contracted disjunctive normal form is the disjunction of all its simple hypotheses; a contracted conjunctive normal form is the conjunction of all its simple consequences. A contracted disjunctive normal form has important applications. The first problem which should be mentioned is the minimization of functions of the algebra of logic, which is a part of the problem of synthesis of control switching systems. The minimization of functions of the algebra of logic consists in constructing a disjunctive normal form for the given function of the algebra of logic which realizes this function and has the smallest sum of the number of factors in its elements, i.
Such disjunctive normal forms are called minimal. Each minimal disjunctive normal form for a given function of the algebra of logic which is not a constant is obtained from the contracted disjunctive normal form of this function by discarding a number of elements. For certain functions the contracted disjunctive normal form may coincide with the minimal disjunctive normal form.
Such a case occurs, for example, with monotone functions, i. In the language over , when the sign is interpreted as addition modulo , the following relations are valid:. These formulas make it possible to translate formulas from the language over into equivalent formulas in the language over , and vice versa. The identity transformations in the latter language are realized with the aid of equalities established for the conjunction and the following additional equalities:. Here it is considered, as before, that conjunction is a stronger connective than the sign.
These equalities are sufficient to deduce any valid equality in the language over , with the aid of identity transformations, just as in the case of the language over. A proposition in this language is called a reduced polynomial if it is of the form , when is equal to 1 or is a variable or a conjunction of various variables without negations, if , , or else is equal to.
- General observations.
- Lazarus Kaine.
- Basic Gates and Functions.
Thus, the expression is a reduced polynomial. Any formula of the algebra of logic may be converted to a reduced polynomial by identity transformations. The equality is valid if and only if the reduced polynomial for is identical with the reduced polynomial for. In addition to the languages mentioned above there are also other languages equivalent to them. Two languages are called equivalent if each formula in one language can be converted, by means of certain conversion rules, into another equivalent formula in the second language, and vice versa.
It is sufficient to base such a language on an arbitrary system of operations and constants such that the operations and constants of the system may be used to represent any function of the algebra of logic. Such systems are said to be functionally complete. Examples of complete systems are , , , etc. There exists an algorithm which can be used to establish the completeness or incompleteness of an arbitrary finite system of functions of the algebra of logic. It is based on the following fact.
A system of functions of the algebra of logic is complete if and only if it contains functions and such that and , as well as functions and , where , is not monotone, and the reduced polynomial of contains an element with more than one factor. There are also other languages based on systems of operations which are not functionally complete, and the number of such languages is infinite. They contain infinitely many pairwise incomparable languages in the sense that there is no way of translating from one language to another by means of identity transformations.
However, for any language based on some operations of the algebra of logic there exists a finite system of equations in this language such that any equality can be deduced with the aid of identity transformations of the equations of this system. Such a system called a deductively complete system of equalities in this language. In considering one of the languages discussed above in conjunction with some complete system of equalities in this language, a tabular statement of the basic operations in the language and the requirement that propositions be the values of its variables are sometimes discarded.
Instead, various interpretations of the language are permitted. These interpretations involve some set of objects which are used as values of the variables and some system of operations over the objects of this set, which satisfy the equalities from a complete system of equalities of the language. Historically, the development of the algebra of logic has been stimulated mainly by the problems to which it has been applied. Who is telling the truth?
- MA111: Introduction to Mathematical Reasoning!
- A Discovery about Basic Logic.
Since we have an additional person there will be twice as many rows in the truth table, but the principles remain the same. Can you work out how this proposition corresponds to the original problem?
The only possible solution is when A, B and C are all knaves. Unfortunately, there is no one the sailor can trust…. After years of sailing across the ocean, Odysseus arrives in the remote city of Mathigon. He wants to ask the Oracle for the directions home, but the gate to the temple of wisdom is guarded by three gods: A pollo, B acchus, and C hronos. One of the gods always tells the truth, one of them always lies, and one god tells the truth and lies at random. The gods understand English, but they always answer in Olympian.
The Olympian words for yes and no are ho and to , but it is unknown which way round. How should Odysseus proceed?
Boolean algebra (structure)