propositional logic and quantifiers

Logic is the grammar of careful argument: a way to state claims exactly and combine them without ambiguity. A proposition is a statement that is either true or false — '3 is odd' (true), 'every string is empty' (false). From small propositions we build big ones using connectives: AND (both must hold), OR (at least one holds), NOT (flips true and false), and implication 'if P then Q' (P forces Q, written P → Q). The everyday word 'or' is exclusive ('soup or salad'), but logic's OR is inclusive — true when either side, or both, is true.

To talk about many things at once we use quantifiers. 'For all' (the universal quantifier, written ∀) claims something about every item: 'for every string w, w is in Σ-star'. 'There exists' (the existential quantifier, written ∃) claims at least one item works: 'there exists a string of length 5'. The single most useful skill is negating a quantified statement, and the rule is a clean flip: the negation of 'for all x, P(x)' is 'there exists an x with not P(x)', and the negation of 'there exists x with P(x)' is 'for all x, not P(x)'. To deny that everyone passed, you exhibit one person who failed.

This flipping is the exact move that turns the pumping lemma into a non-regularity proof. The pumping lemma says: for every regular language there exists a pumping length p such that for all long strings there exists a split that can be pumped. Negating it to disprove regularity flips every quantifier in turn — so the proof becomes: for every p, there exists a bad string such that for every split, pumping breaks it. Getting the alternation of for-all and there-exists right, and negating it correctly, is the whole game.