منطق و سورها
Logic and Quantifiers
مباحث منطق و سورها.
ریاضیات گسسته کنکور ارشد علوم کامپیوتر
کارتها · 16
To negate a quantified sentence, push the negation inward: flip every quantifier ( ∀leftrightarrow∃ ) in order and negate the innermost predicate, turning ∧/∨ and → by De Morgan.
Translate natural language by pairing ∀ with → and ∃ with ∧ ; remember ∀ distributes over ∧ and ∃ over ∨ (and never the mismatched pairs).
An argument is valid (and Γ⊨φ holds) exactly when no interpretation makes all premises true and the conclusion false, so one counterexample is enough to refute it.
DNF is an OR of ANDs of literals and CNF is an AND of ORs of literals; every propositional formula is logically equivalent to one of each.
A set of connectives is functionally complete if it can express every truth function; ¬, ∧ , ¬, ∨ , and ¬, → all qualify, and the single connectives NAND ( ) and NOR ( downarrow ) each suffice on their own.
Prove propositional formulas with introduction/elimination rules arranged into a derivation tree, discharging temporary assumptions via → I ; the system is both sound (only valid conclusions follow) and complete (every tautology is derivable).
"if" introduces the hypothesis, "only if" the necessary consequent, and "unless" means "if not" — three connectives, three fixed implication patterns that konkur loves to swap.
Count the truth assignments that make a formula true by exploiting free variables, shared-head case splits, and the 2^r - 1 rule for a single clause.
To decide if a first-order formula is true, plug the structure's domain and the interpretations of its predicate/function symbols into the formula, then evaluate atoms, connectives, and quantifiers over that domain.
A consistent set is satisfiable by some valuation; a maximal consistent one decides every proposition, and Lindenbaum's lemma says every consistent set extends to one.
An occurrence of a variable is bound when it lies inside the scope of a quantifier on that same variable, and free otherwise. Count occurrences, not names, and remember a quantifier's scope stops at its subformula.
Rewrite A -> B as not A or B, then distribute. A conjunction/disjunction in the CONSEQUENT splits cleanly; in the ANTECEDENT the connective FLIPS, so (P or Q) -> R becomes a conjunction.
Decidable = an algorithm always halts with the right yes/no; recursively enumerable (r.e.) = halts only on the YES-instances. Every decidable set is r.e., but not conversely — and the gap is exactly where logic problems live.
A base of a set of propositions Γ is a subset that proves all of Γ yet has no redundant member — a minimal generating set for the deductive closure of Γ .
A function defined by recursion on a formula's parse tree is pinned down by structural induction; when each connective contributes a distinct prime factor, unique factorization reads back every connective count from the single value f(A).
To turn an n-element universe into a structure you interpret each symbol independently and multiply: a k-ary relation gives 2^(n^k) choices, a k-ary function gives n^(n^k), and a constant gives n.