Tagged Questions

36 views

Subproof in Fitch style system

When using a Fitch style system for proving various theorems, why are we allowed to assume anything we want in the assumption of a subproof in order to derive some desired result? It seems like there ...
45 views

Conjuctive Normal Form

In Boolean logic, a formula is in conjunctive normal form or clausal normal form if it is a conjunction of clauses, where a clause is a disjunction of literals; otherwise put, it is an AND of ORs. I ...
58 views

Natural Deductions of Propositional Logic and Predicate Logic

I'm trying to prove the following: ¬(A --> B) ⊢ ¬(¬A v B) ¬(¬A v B) ⊢ (A ^ ¬B) ∀x∀y(P(x, y) --> ¬P(x, y)) ⊢ ∀x¬P(x, x) For the first two, I feel like the first step is try assume the ...
Consider: $A1: \textbf{0} \not = x'$ $A2: x'=y' \rightarrow x = y$ $A3: \neg x < \textbf{0}$ $A4: x < y' \leftrightarrow (x < y \vee x = y)$ $A5: \textbf{0} < y ... 2answers 106 views How to write negation of statements? How to write negation of following statements in words? ... 2answers 68 views Convert this solution to inference notation This is a proof for De Morgan's Law. Could you help me convert this to inference notation so I can understand the proof better? I find it hard reading this, specifically, which line each assumption ... 2answers 118 views First-order logic: how-to produce interpretation where a given formula is false? For example, given Theory T with predicates $$A(x), B(x), C(x,y), D(x,y), x=y$$ axioms $$\exists x.A(x) \land \exists x.B(x) \land \exists xy.C(x,y)\\ \forall x(A(x) \leftrightarrow \neg B(x)),$$ ... 1answer 205 views Tracing a most-general unifier algorithm I'm trying to trace the algorithm for getting the most general unifier, and I'm a bit confused. Can there be more than one solution? (although the adjective 'most' suggests otherwise) found online: ... 1answer 149 views Soundness of a rule of a proof system with respect to the truth tables? I have the following question: "Explain the concept of the soundness of a rule of a proof system with respect to the truth tables" Would it be correct to state the following: "A rule of a proof ... 2answers 36 views Propositional logic-Predicates I have this problem in my Discrete structures course Show why : ∀x P(x) ∨∀x Q(x) is not logically equivalent to ∀x(P(x)∨Q(x)) . Please help solve this 0answers 15 views predicate calculus and using the Euclidean algorithm [duplicate] So I have this problem which I can't seem to prove. Define the predicate RP(a,b) for positive naturals a and b as follows. RP(a,b) is defined to be true if and only if one of the following is true: ... 1answer 102 views Discrete math proof issue This is a question from my discrete math quiz. I was asked to prove there exists a Q(x). I used Disjunctive Syllogism to prove it. I was marked incorrectly because I used two different variables in ... 1answer 60 views Making first order logic statements I'm working on an assignment that deals with predicate calculus, and I'm trying to put sentences into first order logic statements. I've got the hang of most of them, but I'm not quite sure how to do ... 1answer 73 views Glivenko's theorem in predicate logic Is it possible to extend Glivenko's theorem, which states: If$\Gamma$is a set of propositional formulas and$\phi$is a propositional formula, then$\Gamma$proves$\phi$using classical logic if ... 1answer 61 views a fundamental clarification about predicate expression (formula) I have few foundation questions to be clear about expression involving predicates.$\forall n\in \Bbb N.p(n) \tag {1.2}$Here the symbol$\forall$is read “for all.” The symbol$\Bbb N$... 1answer 92 views Some doubts about interpretation of an atomic formula in predicate calculus I have some doubt related to the interpretation of atomics formulas in predicate calculus. In predicate calculus a formula will be interpreted on a specific domain that is where I take the allowed ... 1answer 104 views Some doubts about predicate calculus I am studying the predicate calculus in First Order Logic and I have some doubt about this argument. In my book I find that a formula in the predicate calculus is built from Literals constructed ... 2answers 347 views Some doubts about the differences between logic implication and inference rule I am studying for an Artificial Inteligence university exam that includes a section dedicated to mathematical logic. I am finding some difficulty in understanding the difference between logical ... 1answer 208 views What does it mean that a set S tautologically implies wff$\tau$What does it mean that a set$S$tautologically implies wff$ \tau$? in Enderton introduction to mathematical logic , in page 23 , it define that a set$S$tautologically implies wff$ \tau$iff ... 1answer 74 views what is the difference between formula and the abbrevation of a formula? there is a problem which is asking me to determine whether a string is a formula or an abbrevation of a formula but i don't know the diffrence of formula and the abbrevation of a formula i know ... 2answers 433 views what is the definition of an interpretation of first order theory$T$? what is a model for$T$? what is the definition of an interpretation of first order theory$T$? what is a model for$T$? can you give me the definition supported with some simple examples ? i read the definition in ... 2answers 231 views What are the rules for the use of dots rather than parentheses in logical formulae? What are the rules of omission of parentheses of formulas in mathematical logic ? in my text , first order logic mathematical logic by angelo margaris ed 1990 dover , the paretheses is omitted for ... 3answers 1k views How does “If$P$then$Q$” have the same meaning as “$Q$only if$P$”? Every lecture that I watched on mathematical logic and my textbook say that$P \Rightarrow Q$has the same meaning as$\text{"If $P$ then $Q$"}$which has the same meaning as$\text{$Q$ only if ...
We have the axioms: $\vdash x = y \to (A\to A')$ where $A'$ is the formula which is created by replacing some of the free apperances of $x$ in $A$ by $y$ $\vdash x=x$ for all $x$ We need to prove ...