Questions about logic and mathematical logic, including model theory, proof theory, computability theory (a.k.a. recursion theory), and non-standard logics. Consider using one of the following tags: (model-theory), (set-theory), (computability), (proof-theory) if they fit the question.

learn more… | top users | synonyms (1)

1
vote
2answers
7 views

Difference between these two statements

$\forall x\in S, \forall z\in S,\exists y\in C, (x\neq z) \Rightarrow ...$ $\forall x\in S, \forall z\in S, \exists y\in C,...$ Why is there a need for $x \ne z$ in 1. Isn't it already implied that ...
0
votes
2answers
21 views

Logical equivalence: Which side is better to start to obtain the other?

How to resolve this with steps please: $$p \to (q \lor r) \equiv (p \to q) \lor (p \to r)$$ I just don't get how with less variable we can have more after or with more we can have less?
1
vote
0answers
17 views

predicate-logic - I think these claims are equivalent, can you verify please?

T is a set of natural numbers. c1: if 2 is the only prime number that divides elements of T. c2: all elements of T are equal to 2^n, where n is a natural number. I'm pretty sure c1 implies c2, ...
0
votes
2answers
18 views

Trouble with a theorem in Hunter's Metalogic

I'm a logician studian and I'm reading Hunter's Metalogic. I'm having trouble understanding and exemplifing part of a theorem in the book. It's the theorem 40.14, pp. 156-7. 40.14. Let t and u be ...
1
vote
2answers
24 views

Find logic expression for given truth table

So I was given this truth table and I needa find a logical expression for the formula to give such result (where there can be two or three 2-place connective expression (e.g. A v B counts as one but ...
1
vote
2answers
34 views

When is $\neg(x\le 21\iff x>15)$ true?

Let $x$ be a real number. I want to find for which $x$ the following statement $\neg(x\le 21\iff x>15)$ holds. I believe it is true when $x\in(-\infty,15)\cup[21,\infty)$, but I don't know how to ...
1
vote
1answer
35 views

Simplifying Circuits

I have a question regarding simplifying a circuit of a function below that has 5 logic gates in original. f = (A + B) * (C + D) + (A + B) * (C + D)' + C = (A + B) * ((C + D) + (C + D)') + C = (A ...
3
votes
1answer
23 views

Problems in formalizing these sentences

This is the first sentence that I have to formalize: "Every student likes at least one type of cake" Let: $S(x)$ stands for 'x is a student' $C(x)$ stands for 'x is a type of cake' $L(x,y)$ ...
0
votes
2answers
40 views

Weird logic question I need help with!

The professor tells Jim: "It is necessary that you get at least a B on the final in order to pass the course". Jim gets a B. What can she conclude? a) He passed b) He can conclude nothing... I ...
2
votes
1answer
18 views

Prove $ \vdash \alpha \to \alpha $ in minimal logic of Hilbert

$ \vdash \alpha \to \alpha $ I'm trying to find a way solving this statement using minimal logic of Hilbert which have only two axiom's K & S and one only rule the modus pones (MP) : ...
2
votes
1answer
18 views

Proving a variable true through rules of inference

Question: Use rules of inference to show that if $(p → q) ∧ (q → p),\; t ∨ q,\; t ∨ p,\; (p ∧ q) → t$, then $t$ is true. Work So Far: $$\text{1. }(p \implies q) \land (q \implies p)\text{ | ...
3
votes
1answer
14 views

Boolean Algebra: Converting $xy'z + wxy'z' + wxy + w'x'y'z' + w'x'yz' = w'x'z' + xy'z + wx$

Notation w,x,y,z are all just primary statements "+" is the OR logical operator what looks like two or more statements being multiplied is actually the AND operator The complement or prime ...
0
votes
1answer
28 views

Predicate Logic Question: Implications/Operations on the Empty Set

Suppose T is a set of Natural numbers. C1: $2$ is the only prime number that divides elements of $T$ C2: $T$ is the set of all natural numbers that satisfy the quadratic equation $x^2+x+1=0$. I'm ...
3
votes
2answers
41 views

What is the modus ponens of a tautology?

In the statement $P$ and $Q$, please show that $\; (P \land (P \Rightarrow Q))\Rightarrow Q \;$ is a tauntology. The state the $\;(P \land (P \Rightarrow Q))\Rightarrow Q\;$ in words. I know I need ...
1
vote
2answers
91 views

Prove $x' \neq x$ using Peano axioms

I am looking at Edmund Landau, Foundation of analysis and do not agree with is proof of Theorem 2 part 2. I put the pages here for easy reference (http://pbrd.co/1y89p7b and http://pbrd.co/1y89A2s). ...
0
votes
1answer
19 views

Satisfiability of the resolvent

What would be a way to prove the following statement: S = {$C_1$, $C_2$} and C is the resolvent of $C_1$, $C_2$. By resolvent I mean the result of the resolution operation. The theorem: if S is ...
0
votes
1answer
24 views

Please help with understanding a logic definition: Subformula

Alright, so I am reading "Computability and Logic" by Boolos and Jeffrey, specifically I'm on chapter 9 "A Precis of First-Order Logic: Syntax. There has been more than a handful of definitions in ...
1
vote
3answers
55 views

Propositional Logic : Why is ((p $\Rightarrow$ r) $\land$ (q $\Rightarrow$ r)) $\equiv$ ((p $\lor$ q) $\Rightarrow$ r)

I was working my way through some Propositional Logic and had the following doubt : Why is this true : ((p $\Rightarrow$ r) $\land$ (q $\Rightarrow$ r)) $\equiv$ ((p $\lor$ q) $\Rightarrow$ ...
3
votes
1answer
34 views

Should $x$ be not free in $\beta$ to prove $\vdash [ \forall x(\beta\rightarrow \alpha)\rightarrow (\exists x\beta\rightarrow \alpha)]$?

Should $x$ be not free in $\beta$ to prove $\vdash [ \forall x(\beta\rightarrow \alpha)\rightarrow (\exists x\beta\rightarrow \alpha)]$? In "Mathematical Introduction to Logic, Enderton" This is an ...
0
votes
1answer
71 views

In Whitehead & Russell's PM, what makes anything true or false?

It seems that truth and falsehood are fundamental to meanings and types. A proposition is defined as anything that is true or that is false. PM defines truth as "consisting in the fact that there is ...
0
votes
1answer
23 views

$p\to\neg q, q \vdash \neg p$- natural deduction

I have the following proposition: $$p\to\neg q, q\vdash \neg p$$ Using the following formulas on propositions is easy enough: $$\frac{\psi \qquad \psi\to\varphi}{\varphi}\quad \to_e$$ ...
0
votes
1answer
45 views

prove $( \lnot \lnot p \Rightarrow p) \Rightarrow (((p \Rightarrow q ) \Rightarrow p ) \Rightarrow p )$ with intuitionistic natural deduction

I'm trying to prove this statement with intuitionistic natural deduction using inference rules like this example : this is the statement I'm trying to solve : $$( \lnot \lnot p \Rightarrow p) ...
2
votes
1answer
25 views

$p \to (q\vee\neg r), \neg q, r ⊢ \neg p$ - Natural deduction- elimination with $\neg$ operator

I have the following proposition: $$p \to (q\vee\neg r), \neg q, r ⊢ \neg p$$ The only part I have trouble with is the : $$p \to (q\vee\neg r)$$ Clearly the first step is to eliminate $q$ or $\neg ...
2
votes
0answers
56 views

Vague predicates in standard predicate logic [on hold]

I'm trying to work out if a sentence of the form: 'Bob is larger than Maureen and almost as large as Chris' can be adequately formalised in predicate logic. One could just write: ...
2
votes
3answers
48 views

What is the correct form of De Morgan's Law in logic?

According to wikipedia (link), Morgan's Law is: $$¬ (P \wedge Q) \Rightarrow (¬P) \vee (¬Q)$$ But if you scroll down to 8.2.2 on this page (link), it says that Morgan's Law works as follow: $$¬ (P ...
0
votes
1answer
33 views

Prove tautology without truth using a truth table. [duplicate]

I am struggling to prove, without using truth tables, that the statement is a tautology. [(p→q)∧(q→r)]→(p→r) My work so far... ¬[(¬p∨q)∧(¬q∨r)]∨(¬p∨r) ...
-1
votes
0answers
19 views

Prove that Boolean algebra P(S) is isomorphic with the product. [on hold]

Could you help me with this please? From the begining to the end?
-1
votes
0answers
55 views

How to prove if ∀y(∃x(sx = y) ∧ ∃x(sy = x)) is logically valid [on hold]

I first tried to prove whether this statement is logically true or not, by negation and then attempted to substitute. However I can't get a clear answer and am now quite puzzled. Could someone please ...
-1
votes
1answer
28 views

Proof that the formula $((p\to q)\land (q\to r)\land p)\to r$ is a tautology [duplicate]

Write down the assumptions in a form of clauses and give a resolution proof that the formula is a tautology. $((p\to q)\land (q\to r)\land p)\to r$ I got information that i need to use here ...
0
votes
1answer
18 views

Query to get all employees that report to themselves.

I have two predicates: $Employee/1$ and $ReportsTo/2$ and let's say we have two constants: $Patrick/0:$ and $Octo/0:$ The predicate $ReportsTo/2$ takes two Employees, one reports to the other. It ...
0
votes
1answer
39 views

Question about $p \implies q$ predicate logic

$T$: a set of natural numbers. $S_1$: $2$ is the only prime number that divides elements of $T$. $S_2: T = \{16, 8, 528\}.$ I'm trying to figure out which statements imply each other, i.e., does ...
1
vote
0answers
24 views

Truth table for $(p \implies q) \lor (q \implies r) \lor (r \implies p)$ : What should my next step be?

I am working on a truth table for $(p \implies q) \lor (q \implies r) \lor (r \implies p)$ This is what I have done so far: My next step would be to do the disjunction from the first two ...
1
vote
1answer
47 views

Theory of definitions

I am reading "Introduction to Logic" by P Suppes at the moment. In the Chapter 8 - Theory of definitions of it, I 've some confusion, actually about the Conditional Definition. The brief explanation ...
2
votes
1answer
47 views

Couple of questions from Takeuti's Proof Theory book

I am reading Gaisi Takeuti's Proof Theory (Second Edition, Dover), and I have a couple of questions: I) Right after the first (1.1.) definition, the author says that "In any case it is essential that ...
-1
votes
0answers
36 views

Relations commuting with logical equivalence.

I'm looking for theorems of the form, 'Relation X commutes with logical equivalence', where X is NOT uniform substitution. What's the best place to find such theorems?
0
votes
0answers
35 views

What does it mean? [on hold]

I tried to do this but i dont know what it's exactly mean. Please help me someone i have exam soon!
1
vote
2answers
35 views

Negating the Sentence with 'because'

I have to negate the sentence "They pushed us into a big white room and I began to blink because the light hurt my eyes." My main issue is I'm unsure how the word 'because' can be negated. If P="I ...
2
votes
1answer
37 views

Is the $\varphi \to \varphi$ axiom in Hilbert calculus redundant?

When I see the Hilbert calculus in logic, I sometimes notice that $T \vdash \varphi \to \varphi$ is listed as an axiom and sometimes not. Is there some reason? Could I get it somehow from the other ...
0
votes
2answers
35 views

Negate definition of limit [on hold]

The definition for $\lim \limits_{x\to a} f(x) = L$ is the following: For all real numbers $\varepsilon > 0$, there is a real number $\delta > 0$ such that for all real numbers $x$ if $a−\delta ...
3
votes
1answer
17 views

Find X so that $(p \Longleftrightarrow ¬q) ∧ (r ⇒ X) ∧ (¬r ⇒ ¬X)$ is contradiction

I have to find X so that this $(p \Longleftrightarrow ¬q) ∧ (r ⇒ X) ∧ (¬r ⇒ ¬X)$ is a contradiction. Then I also have to find out whether or not I can find an X is a tautology. What's the most ...
0
votes
1answer
28 views

how to prove $ B = ( \beta \Rightarrow \gamma) \Rightarrow (\alpha \Rightarrow \beta)\Rightarrow \alpha\Rightarrow \gamma $ using natural deduction

I tried to follow a similar question solving another statement using natural deduction but it still seems hard to understand every time I get a different solution I can't figure out a methodology to ...
2
votes
1answer
45 views

Prove $\forall z\left(\left(\exists xA\rightarrow A_{x}[z]\right)\rightarrow B\right)\vDash B$

I'm doing some self-exercises on mathematical logic by myself and have come across this question which I can't seem to prove: Let $A$ be a formula with a single free variable $x$. Let $B$ be a ...
1
vote
1answer
37 views

Negation of uniform continuity

The definition of uniform continuity is: Given any $\varepsilon>0\ \exists\delta>0\ \forall x\in I \ \forall y\in I\ \left(\text{if }|x-y|<\delta\text{ then }\ ...
0
votes
0answers
26 views

EC,PC elementary class,pseudolementary class,omitting types

What are the typical examples of PC (pseudoelementary class) with and without omitting types, which are not elementary with and without the omitting types, respectively?
0
votes
0answers
21 views

Contrapositive/contradiction of statement with quantifiers

In general how does one formulate a proof by controposition or contradiction for the following general form: $\forall x\exists ! y (P(x)\wedge Q(y) \rightarrow R(x,y))$ Or more specifically: $\forall ...
4
votes
4answers
79 views

Show that $(p \to q) \lor (q \to p)$ is a tautology

i tried to prove that $(p \to q) \lor (q \to p)$ is tautology i used p and not-q as conditions. (Premises 1 and 5) I managed to get to a solution but I'm not sure if it's right. can you please check ...
0
votes
3answers
8 views

Logical Arguments: Why is this Multiple Argument Invalid?

In my understanding, an argument is valid when it is the case that if the premises are true, then the conclusion must be true. I have been given the following argument that if $n$ is both a multiple ...
0
votes
2answers
36 views

How can i get a tautology truth table from using 3 variables?

I am looking to use the variables p, q and r to create a truth table which concludes to a tautology.
0
votes
1answer
39 views

Proving an “OR” statement

If one wants to proof $P\vee Q$, is it sufficient to proof $\lnot P \rightarrow Q$? Because it makes intuitively more sense to me that $P\vee Q$ would be logically equivalent with $(\lnot P ...
0
votes
0answers
18 views

How do I prove double negation elimination in a propositional logic axiom system?

Here are my axioms: $X \rightarrow (Y \rightarrow X)$ $(X \rightarrow (Y \rightarrow Z)) \rightarrow ((X \rightarrow Y) \rightarrow (X \rightarrow Z))$ $(\lnot Y \rightarrow \lnot X) \rightarrow ...