Fundamentals of Computer Science - Week 1 Summary - Part 1 out of 2
1.1 Propositional logic
What is propositional logic?
It's a system that deals with propositions or statements.
What is a proposition? What is a statement?
Proposition is a statement that can be either true or false. It must be one or the other. Cannot be both.
Examples:
2 is a prime number // true
5 is an even number // false
Examples of sentences that are not propositions
* Sentences whose truth value depends on variables are not propositions.
* Questions and imperatives are not propositions.
X is a prime number // can't tell since it can be both as we don't know X
Are you going to school? // cannot assign a truth value because it's a sentence
Do your homework // sentence is an order. has no truth value
Notations of propositional logic
* Propositions are denoted by CAPITAL letters, P, Q, S, ...
* P = carrots are orange
* Q = I went to a party yesterday
* General statements are denoted by lowercae letters, p, q, ...
* unspecified truth values are also called propositional variables
We can use connectives to change or combine the meanings of propositions.
See https://en.wikipedia.org/wiki/List_of_logic_symbols
* Logical NOT (also called negation) ¬
* ¬p is true if and only if p is false.
* Logical OR (also called disjunction) ∨
* p ∨ q is true if one of them is true.
* Logical AND (also called conjunction) ∧
* p ∧ q is true if both of them are true.
* Logical IF...THEN (also called conditional or implication) →
* p → q where p is the premise and q is the conclusion
* p → q is true if and only if either p is fale or q is true
* Logical IF and only IF ↔
p ↔ q is true if and only if both p and q are true
* Exclusive OR: XOR ⊕
* p ⊕ q is true if p or q is true but not both
Truth table: example
* Truth table is a set of all possible outcomes of propositions and connectives.
* The number of rows in a truth table depends on the number of given propositions. If we have n propositions in our formula, our truth table will have 2^n.
Basic Connectives
* Negation: can be thought as one minus the truth value of p
* Conjunction: will give a true truth value when both propositions are true. Mathematically think of it as multiplication. T(p) x T(q).
* Disjunction: will be true if at least one of the propositions is true (can be thought as maximum of p and q)
* Conditional or implication: Think of implication as a promise. For example, if you study hard, then I will give you a cookie. I only break this promise if you actually study hard and I don't give you the promised cookie. Otherwise, I have not broken this promise. So if you don't study and I decide to give you the cookie, this connective is a still true.Mathematically, think of it as less than or equal to p then q is the same as p is less than or equal to q.
Other connectives
* bi-conditional: will be true when p and q have the same truth value. You can think of it as an equality check.
* Exclusive OR: will be true if only one of p or q is true. It's the opposite of bi-conditional
Operator precedence for propositional logic
¬ ∧∨ → ↔
1.2 Tautology and consistency
Tautology
* A formula that output is always true no matter the truth values of the propositions
* Not all formula is a tautology
* Example: p∨¬p
* (p∧q)→p
* (p∧q)→q
Consistent
* A formula that is true at least for one scenario
* Example: p∧q
* All the connectives are consistent
Not consistent
* Not consistent or inconsistent is a formula that is never true
* It's also called contradiction
* Example: p∧¬p, (p∧¬p) (p∧¬p)
Essencial reading
Rosen, K.H. Discrete mathematics and its applications (New York: McGraw-Hill, 2012) 7th edition, Chapter 1.1-1.2, pp.1-22.
What is propositional logic?
It's a system that deals with propositions or statements.
What is a proposition? What is a statement?
Proposition is a statement that can be either true or false. It must be one or the other. Cannot be both.
Examples:
2 is a prime number // true
5 is an even number // false
Examples of sentences that are not propositions
* Sentences whose truth value depends on variables are not propositions.
* Questions and imperatives are not propositions.
X is a prime number // can't tell since it can be both as we don't know X
Are you going to school? // cannot assign a truth value because it's a sentence
Do your homework // sentence is an order. has no truth value
Notations of propositional logic
* Propositions are denoted by CAPITAL letters, P, Q, S, ...
* P = carrots are orange
* Q = I went to a party yesterday
* General statements are denoted by lowercae letters, p, q, ...
* unspecified truth values are also called propositional variables
We can use connectives to change or combine the meanings of propositions.
See https://en.wikipedia.org/wiki/List_of_logic_symbols
* Logical NOT (also called negation) ¬
* ¬p is true if and only if p is false.
* Logical OR (also called disjunction) ∨
* p ∨ q is true if one of them is true.
* Logical AND (also called conjunction) ∧
* p ∧ q is true if both of them are true.
* Logical IF...THEN (also called conditional or implication) →
* p → q where p is the premise and q is the conclusion
* p → q is true if and only if either p is fale or q is true
* Logical IF and only IF ↔
p ↔ q is true if and only if both p and q are true
* Exclusive OR: XOR ⊕
* p ⊕ q is true if p or q is true but not both
Truth table: example
* Truth table is a set of all possible outcomes of propositions and connectives.
* The number of rows in a truth table depends on the number of given propositions. If we have n propositions in our formula, our truth table will have 2^n.
Basic Connectives
* Negation: can be thought as one minus the truth value of p
* Conjunction: will give a true truth value when both propositions are true. Mathematically think of it as multiplication. T(p) x T(q).
* Disjunction: will be true if at least one of the propositions is true (can be thought as maximum of p and q)
* Conditional or implication: Think of implication as a promise. For example, if you study hard, then I will give you a cookie. I only break this promise if you actually study hard and I don't give you the promised cookie. Otherwise, I have not broken this promise. So if you don't study and I decide to give you the cookie, this connective is a still true.Mathematically, think of it as less than or equal to p then q is the same as p is less than or equal to q.
Other connectives
* bi-conditional: will be true when p and q have the same truth value. You can think of it as an equality check.
* Exclusive OR: will be true if only one of p or q is true. It's the opposite of bi-conditional
Operator precedence for propositional logic
¬ ∧∨ → ↔
1.2 Tautology and consistency
Tautology
* A formula that output is always true no matter the truth values of the propositions
* Not all formula is a tautology
* Example: p∨¬p
* (p∧q)→p
* (p∧q)→q
Consistent
* A formula that is true at least for one scenario
* Example: p∧q
* All the connectives are consistent
Not consistent
* Not consistent or inconsistent is a formula that is never true
* It's also called contradiction
* Example: p∧¬p, (p∧¬p) (p∧¬p)
Essencial reading
Rosen, K.H. Discrete mathematics and its applications (New York: McGraw-Hill, 2012) 7th edition, Chapter 1.1-1.2, pp.1-22.
Comments
Post a Comment