CPE 122.pdf

TERMS BASIC CONCEPTS IN LOGIC LOGIC – It is the study of reasoning and is concerned with the correctness of the reasoning PROPOSITION – It is a declarative...

TERMS BASIC CONCEPTS IN LOGIC LOGIC – It is the study of reasoning and is concerned with the correctness of the reasoning PROPOSITION – It is a declarative sentence or a sentence that declares a fact – It is a sentence that is either true or false, but not both – Sometimes called Statements PROPOSITIONAL – aka Statement Variables VARIABLES – These represent propositions, just as letters used to denote numerical variables – The commonly used variables are p, q, r, s, … and uses lowercase letters TRUTH VALUE – The truth value of a proposition is true, denoted by T, if it is a true proposition, and the truth value of a proposition is false, denoted by F, if it is a false proposition. TRUTH TABLE – A table which summarizes the truth value of propositions. SIMPLE PROPOSITION – These are sentences that are made only by a single statement. COMPOUND – New propositions formed from existing propositions using logical operators. PROPOSITION TAUTOLOGY – Is denoted a tautology by t. – It is a compound proposition that is always true, regardless of the truth values of the propositional variables. CONTRADICTION – A compound proposition that is always false and is denoted by f. CONTINGENCY – A compound proposition that is neither a tautology nor a contradiction. LOGICALLY – The compound propositions p and q if p ↔ q is a tautology EQUIVALENT – The notation p ≡ q denotes that p and q are logically equivalent LOGICALLY A proposition P is said to logically imply a proposition Q if, whenever P is true, then Q is also true. IMPLY For logical implication all we insist on is that Q is never false when P is true. We denote logical implication by ├ so that ‘P logically implies Q’ is written P├ Q. CONVERSE – The proposition q → p is the converse of the proposition p → q CONTRAPOSITIVE – It is also sometimes referred to as transposition. – The contrapositive of p → q is the proposition ¬q → ¬p INVERSE – The proposition ¬p → ¬q is called the inverse of p → q. THE ALGEBRA OF PROPOSITIONS REPLACEMENT LAWS Idempotent laws (Idem) p∧p≡p p∨p≡p Double Negation law (Doub) -(-p) = p Absorption laws (Absorp) p∧(p∨q)≡p p∨(p∧q)≡p Commutative laws (Comm) p∧q≡q∧p p⊕q≡q⊕p p∨q≡q∨p p↔q≡q↔p Associate laws (Assoc) (p∧q)∧r≡p∧(q∧r) (p∨q)∨r≡p∨(q∨r) (p⊕q)⊕r≡p⊕(q⊕r) (p↔q)↔r≡p↔(q↔r) Distributive laws (Dist) p∧(q∨r)≡(p∧q)∨(p∧r) p∨(q∧r)≡(p∨q)∧(p∨r) Involution law (Invol) -p ≡ p De Morgan’s laws (De M) p ∨ q ≡ -p ∧ -q p ∧ q ≡ -p ∨ -q (dash above)  Identity laws (Ident) p∨f≡p p∨t≡t p∧t≡p p∧f≡f Complement laws (Comp) p ∨ -p ≡ t -f ≡ t p ∧ -p ≡ f -t ≡ f Transposition laws (Trans) p → q ≡ -q → -p Material Implication law (Impl) p → q ≡ -p ∨ q Material Equivalence laws (Equiv) p↔q≡(p→q)∧(q→p) p ↔ q ≡ ( p ∧ q ) ∨ ( -p ∧ -q ) QUANTIFICATION – Another important way to create a proposition from a propositional function. – Quantification expresses the extent to which a predicate is true over a range of elements. – In English, the words all, some, many, none, and few are used in quantifications. DOMAIN OF – It is sometimes referred to as universe of discourse or domain. DISCOURSE – For instance, P(x) is a statement which has a variable x and let D be a set. – We call P as the propositional function (with respect to D) if in each x in D, P(x) is a proposition. – We then therefore call D as the domain of discourse of P. UNIVERSAL – Denoted by the symbol ∀ which is expressed as “for every”. QUANTIFIER – Thus, the statement for every x, P(x) can also be written as ∀𝑥𝑃(𝑥). EXISTENTIAL – Denoted by the symbol ∃ which is expressed as “for some”. QUANTIFIER – Thus, the statement for some x, P(x) can also be written as ∃𝑥𝑃(𝑥). ARGUMENT – It is a set or sequence of propositions. – An argument is valid if the truth of all its premises implies that the conclusion is true. PREMISES – All the proposition in the argument except the final proposition CONCLUSION – The final proposition in an argument. THEOREM – A statement that can be shown to be true. – In mathematical writing, the term theorem is usually reserved for a statement that is considered at least somewhat important. – Less important theorems are sometimes called propositions. AXIOM – A statement that is assumed to be true. LEMMA – A less important theorem that is helpful in the proof of other results COROLLARY – A theorem that can be established directly from a theorem that has been proved CONJECTURE – A statement that is being proposed to be a true statement. PROOFS – Essentially an explanation and communication of ideas. – It is an argument that establishes the truth of a theorem or of a mathematical statement. DIRECT PROOFS A proof that p → q is true that proceeds by showing that q must be true when p is true PROOF BY A proof that p → q is true that proceeds by showing that p must be false when q is false. CONTRAPOSITION VACUOUS AND A proof that p → q is true based on the fact that p is false. TRIVIAL PROOFS PROOFS BY A proof that p is true based on the truth of the conditional statement ¬p → q, where q is a CONTRADICTION contradiction. It is also sometimes called as indirect proof PROOFS OF A proof that p ↔ q is true that proceeds by showing that p → q and q → p are true EQUIVALENCE MATHEMATICAL Proof from mathematical textbooks aim to communicate the essential reasons why a particular PROOFS result holds rather than dwelling on rigorous step-by-step detail.  Argument – Sequence of propositions written as: 𝑝1 𝑝2 ⋮ ------- 𝑝𝑛 ∴ 𝑞 ○ Valid – if 𝑝1, 𝑝2, … 𝑝𝑛 are all true, then 𝑞 must also be true ○ Invalid – otherwise Hypotheses – The propositions 𝑝1 , 𝑝2 , … 𝑝𝑛 Conclusion – proposition 𝑞 RESOLUTION OF PROOFS MATHEMATICAL – An appropriate way to proving that a result holds for all positive integers. INDUCTION – t consists of the following steps: a. Prove that the conjecture holds for n = 1. b. Prove that, for all k ≥ 1, if the result holds for n = k, then it must also hold for n = k + 1. This is known as the inductive step SETS – It is a collection of well-defined objects, called elements (or members) of the set. – The symbol ∈ is referred as ‘belongs to’ or ‘is an element of’ SETS NOTATION – The simplest is by listing the elements enclosed between curly brackets or ‘braces’ { }. – Generally, we use upper-case letters to denote sets and lower-case letters to denote elements. EMPTY SET – Sometimes called a null set, void set, zero set or a vacuous set, which contains no elements. – This set is usually denoted Ø or { }. SINGLETON SET A set that has only one element EQUALITY OF SETS – Two sets are defined to be equal if they contain same elements: A = B if ∀x[x ∈ A ↔ x ∈ B] is a true proposition, and conversely regardless of the order an element appear in each sets. – Also, it Is the standard convention to disregard repeats of elements in a listing. CARDINALITY – If A is a finite set its cardinality, |A|, is the number of (distinct) elements which it contains. – Other notations commonly used for the cardinality of A are n(A), #A and Ᾱ. INFINITE CARDINALITY If A is an infinite number of elements, we say it has infinite cardinality, and write |A| = ∞. UNIVERSAL SET – Contains all objects which are to be considered during some specific discussions. – It is sometimes denoted as the universe or the universe of discourse and is denoted by. POWER SET – Let A be any set. The power set of A, denoted P(A), is the set of all subsets of A:P(A) = {B | B ⊆ A} – For all sets of A and B: a. A ⊆ B if and only if P(A) ⊆ P(B). b. P(A) ⋂ P(B) = P(A ⋂ B). c. P(A) ⋃ P(B) ⊆ P(A ⋃ B). SUBSET – Denoted A ⊆ B, if every element of A is also an element of B. – Symbolically, A ⊆ B if ∀x[x ∈ A → x ∈ B] is true, and conversely. VENN-EULER – A useful visual representation of sets. DIAGRAM – Frequently all the sets in the diagram are placed inside a box which represents the universal set. – If an element belongs to more than one set in the diagram, the two regions representing the sets concerned must overlap and the element is placed in the overlapping region INTERSECTION – The set of all elements which belong to both sets – It is denoted as A ⋂ B. UNION – The set of all elements which belongs to either of the sets or to both sets. – It is denoted as A ⋃ B. DISJOINT Sets are said to be disjoint if they have no elements in common; that is, if A ⋂ B = Ø COMPLEMENT – Consists of all the elements in which do not belong to A. It is denoted as Ᾱ (or A’ or Ac ). – The complement of A is given by Ᾱ = - A. DIFFERENCE / All the elements of the other set which do not belong to the other set, denoted as A – B or A / B. RELATIVE A – B = {x | x ∈ A and x ∉ B} = A ⋂ B  COMPLEMENT CARTESIAN PRODUCT – The Cartesian product, X x Y, of two sets X and Y is the set of all ordered pairs (x, y) where x belongs to X and y belongs to Y: X x Y = {(x, y) : x ∈ X and y ∈Y} – When X = Y, it is usual to denote X x X by X2. This is read as ‘X two’ and not ‘x squared’. ORDER PAIR (x, y) = (x’, y’) if and only if x = x’ and y = y’ NUMBER SYSTEMS DECIMAL NUMBER – A base 10 number system that is from 0 to 9. SYSTEM – It is called a base 10 number system since it has only 10 digits, namely, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. – This number system is what we use in our day-to-day life. BINARY NUMBER – A base 2 number system which is consist of 0 and 1 SYSTEM OCTAL NUMBER – A base 8 number system that is from 0 to 7, namely, 0, 1, 2, 3, 4, 5, 6, 7. SYSTEM – Similarly, it is called a base 8 number system because it has only 8 digits. HEXADECIMAL A base 16 number system that uses 10 digits and 6 letters, that is 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, NUMBER SYSTEM F. The numerical equivalent of each letters are as follows: A = 10, B = 11, C = 12, D = 13, E = 14, F = 15. COMPLEMENTS – Complements are used in many important ways relating to digital computers. – One of its important uses is for logical manipulation. SIGNED-MAGNITUDE Positive number is represented as 0 and 1 for negative and is placed at the leftmost position of the number SIGNED-COMPLEMENT Negates a number by taking its complement. The signedcomplement system can use either 1’s SYSTEM or 2’s complement, but 2’s complement is the most common. RELATIONS RELATION Can also be referred to as a table that lists the relationship of elements to other elements. BINARY RELATION Let A and B be sets. A relation from A to B (or between A and B) is a subset of the Cartesian product A x B. the relation R is the set of all related pairs of elements. We write a R b to denote ‘a is related to b’ to denote (a, b) ∉ Ꞧ or ‘a is not related to b’. If A = B it is also common to refer to R as a relation on A. Vertices – Dots to represent the elements of X. Direct Edge – An arrow to represent relation of element Loop – Used when (x, y) has the same value PROPERTIES OF Let R be a relation on set A. We say that R is: RELATIONS I. Reflexive if and only if a R a for every a ∈ A II. Symmetric if and only if a R b implies b R a for every a, b ∈ A III. Anti-symmetric if and only if a R b and b R a implies a = b for every a, b ∈ A IV. Transitive if and only if a R b and b R c implies a R c for every a, b, c ∈ A EQUIVALENCE – A subset R of A x A is called an equivalence relation on A if R satisfies the following condition: RELATION I. (a, a) ∈ R for all a ∈ A (R is reflexive) II. If (a, b) ∈ R, then (b, a) ∈ R (R is symmetric) III. If (a, b) ∈ R and (b, c) ∈ R, then (a, c) ∈ R (R is transitive) IV. – Whenever R is an equivalence relation and x and y are elements of A such that (x, y) ∈ R, we say that x is equivalent to y. – We use the symbol (~) for an equivalence relation R, we may restate the properties as: I. a ∈ A, a ~ a II. a, b ∈ A, if a ~ b, then b ~ a III. a, b, c ∈ A, if a ~ b and b ~ c, then a ~ c MATRICES OF Set the entry in row x and column y to 1 if x R y and 0 otherwise. RELATION FUNCTIONS – A function from X to Y is a rule that assigns to each element x ∈ X a unique element y ∈ Y. – – Functions are usually denoted by the letters f, g, h, i, etc. – If f is a function from X to Y, we write f : X → Y. – The set X is the domain of the function f and Y the codomain of f, denoted by dom(f) and  codom(f), respectively. If X = Y, then f is said to be a function on X. COMPOSITION OF Given a function f : X → Y and g : Y → Z, we can formulate a new function h : X → Z by h(x) = g(f(x)) FUNCTION SPECIAL TYPES OF A function f : X → Y is called FUNCTIONS I. Injective/Injection – (one-to-one) if x ≠ y implies f(x) ≠ f(y) II. Surjective function/Surjection – (onto) if for every y ∈ Y there exists x ∈ X satisfying f(x)=y III. Bijective/Bijection – if f is one-to-one and onto.  1. Which term in logic is a compound proposition that is always false? - Contradiction 2. Which term is a declarative sentence or a sentence that declares a fact in logic? - Propositions 3. What symbol denotes logical equivalence in logic concepts and theorems? - ≡ 4. What term refers to the combination of all elements which belong to either of the sets or both sets? - Union 5. Binary, octal, and hexadecimal number systems are all examples of what? - Base number system 6. What does a Singleton Set in logic refer to? - A set that has only one element 7. What term refers to the function h(x) formed by combining two functions using the formula h(x) = g(f(x))? - Composition of Function 8. Which term refers to a function f : X → Y which is one-to-one and onto? - Bijection 9. What does a cardinality represent in the context of sets? - Number of elements 10. Which number system uses the letters A to F? - Hexadecimal 11. What is the signed-complement binary of the decimal -29? (Use 8 bits) - 00011101 12. What is the sum of the hexadecimal values: 9AB and BEC ? - 1597 13. What are the following conversions of the answer in Question 13? - Answer in octal (no need to put base-8): 12627 - Answer in binary (no need to put base-2): 0001010110010111 - Answer in decimal (no need to put base-10): 5527 Ans: p q -p -q (-p V q) (-p V q) X -q T T F F T T T F F T F T F T T F T T F F T T T F Reminder to also study on the Venn-Euler Diagram, the functions of the blackboard for the type of test to make a Venn-Euler Diagram is limited so this text was added as a note to study this topic as well.