Hi everyone. We are in October now and the first CSC165 test is right around the corner, so I thought it'd be a good idea to review the course material that we've learnt so far in my SLOG, as some kind of preparation.
Quantifiers
There is really not much about the quantifiers, so far we've learnt the universal quantifier (∀) and the existential quantifier (∃). An important thing to remember is that to prove a universal claim we need to show that there is no counter-example, and to falsify it just one counter-example would do the job. Also, to verify an existential claim giving just one satisfactory example is enough and to falsify it, it is needed to be shown that there are no examples.
Implication, Conjunction, Dis-junction and Negation
Implication is in the form of P ⇒Q, where P is called the antecedent and Q the consequent, it means if P, then Q. Which also means P is necessary for Q to be true and Q is sufficient for P. The only time that an implication is false, is when P is true and Q is false other than this, an implication is always true.A converse of an implication is when P and Q are switched (Q ⇒ P), and when P ⇒Q is equivalent to its converse a double implication is in place (P ⇔ Q). There is also Conjunction(∧)and Dis-junction(∨). Conjunction is when two statements are combined together and they are both true, it is equivalent to the intersection in sets. Conjunction is false, if one of the statements is false. Dis-junction is when two statements are combined together and at least one of them is true. The only time a dis-junction is false is if and only if both statements are false, dis-junction is also similar to union in terms of sets. The symbol "¬", represents negation in logical symbols, negation means exactly what it sounds like and is associated with the word "not" in English. For example: the negation of P ⇒Q is, not(P ⇒Q) ⇔ ¬(P ⇒Q) ⇔ (P ⇒¬Q), and while I'm on the subject of negation, I should mention the word "Contrapositive" as well, this means when an implication is conversed and antecedent and consequent are both negated ( ¬Q ⇒ ¬P). The contrapositive of an implication is equivalent to the implication itself. There are different relations between conjuctions, dis-junctions, implications and negations, such as: ¬(P ⇒Q) ⇔ P∧¬Q, (P ⇒Q) ⇔ ¬P∨Q, ¬(P∧Q) ⇔¬P∨¬Q, ¬(P∨Q) ⇔ ¬P∧¬Q, the last two relations are also know as De Morgan's law. The real magic happens when quantifiers are thrown into the mix as well.
Laws of Arithmetic, Mixed Quantifiers and Proof Outline
Laws of arithmetic such as commutative, associative and distributive are also used in logic and they'll come in handy for proofs. Another important subject to pay attention to is mixed quantifiers, this is important because the order of using an existential claim and a universal claim in a statement matters. For example, there exist an x for all y is different than saying for all y there exist an x, the first statement means that there exist only one x for all the ys, and the second statement means that there exist an x for each y but the value of x can be changed for each different y. Mixed quantifiers is an interesting subject when mixed with implications, conjunctions, disjunctions and sets for transforming an English statement into a symbolic logical format and vice versa. I have a feeling that all the material that we've learned so far were to lay the foundation for proofs, and the first step on how to write a good proof was introduced to us this week, which was the proof outline. Even though I had some previous knowledge about how to write a good proof, I learned something new and that was to always be skeptical of my proofs and to adjust my justifications and comments in writing a proof with the audience that I'm writing for.
Bring on the test!
This Wednesday is going to be the first challenge in CSC165, or technically the second challenge if I count the first assignment and I feel that I'm ready for it, So bring it on Danny. No I'm just kidding, please take it easy on us Prof. Heap.
p.s. I am really enjoying the tutorials.
