1
vote
2answers
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 ...
1
vote
1answer
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 ...
3
votes
1answer
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 ...
1
vote
1answer
34 views

Show that there exists a satisfactory assignment for the unstandard language of arithmetic $\{\textbf{0}, ', <_1\}$

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 ...
2
votes
2answers
106 views

How to write negation of statements?

How to write negation of following statements in words? ...
0
votes
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 ...
1
vote
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)),$$ ...
1
vote
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: ...
3
votes
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 ...
1
vote
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
0
votes
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: ...
1
vote
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 ...
0
votes
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 ...
1
vote
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 ...
2
votes
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$ ...
4
votes
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 ...
0
votes
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 ...
2
votes
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 ...
3
votes
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 ...
0
votes
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 ...
2
votes
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 ...
5
votes
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 ...
3
votes
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 ...
1
vote
1answer
41 views

Axiom of Equivalence For test..

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 ...