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
0answers
14 views

An exercise on first order logic formulas, terms and Polish notation

This is part of my homework (not mandatory and not accredited). Please comment/answer if my reasoning for the exercises is correct, because I'd like to see if I understand the material. I will start ...
0
votes
2answers
33 views

Express AND in terms of OR, XOR, NOT

Is it possible to express the logical AND in terms of XOR, OR, or NOT? The closest I can come is NOT (p XOR q); the only problem is that the case when both p and q are false, this will turn out to be ...
0
votes
0answers
12 views

Birkhoff's completeness theorem

I have two simple questions. A) Does Birkhoff's completeness theorem follow directly from Gödel's completeness theorem? B) Is Birkhoff's completeness theorem constructive in the following sense: ...
1
vote
1answer
13 views

Translation of sentence to logic formula

Here are four sentences: If Jessy moves his truck, Irene will play her guitar Irene will only move her car, if Jessy moves his garbage cans It is not the case, that Jessy will move his ...
4
votes
2answers
56 views

For a complete truth-set $T$ is a countable transitive model satisfying $T$ unique?

Let $T$ be a maximal (in the sense that either $\phi \in T$ or $\phi \not \in T$ for all $\phi \in \mathcal{L}_\in$) set of sentences consistent with $ZFC$. Question For a countable transitive model ...
0
votes
0answers
17 views

Inference using Proof by contradiction and resolution rule [duplicate]

I get stuck in inference. please help me in step by step inference? By using Resolution Rules, and Proof by contradiction from following Knowledge base, we want to understand how we get the answer of ...
8
votes
1answer
351 views

Big Bang Theory Reference to Formal Logic

In the second episode "The Junior Professor Solution" of the 8th season of the Big Bang Theory, there exists a brief moment where Sheldon Cooper references one of his boards with what for a brief ...
3
votes
2answers
70 views

In Whitehead & Russell's PM, what is the name of that symbol in series of segments?

See the last line. It looks like an unfinished S. Thanks!
0
votes
1answer
76 views

Does $ \sqrt{2} \in R $? [duplicate]

Find a counter-example for this statement, where the domain for all variables consists of all real numbers. $$ \forall x (x^{2} \ne 2) $$ So, does the $ \sqrt{2} $ belong to the set of real numbers? ...
1
vote
1answer
11 views

Equivalence of Quantified Predicates

I'm in Discrete Math and I copied down some rules in my notes. Unfortunately I'm not sure if I made a typo or not, let me show you what I mean. Equivalence of Quantified Predicates Symmetry of 'All' ...
1
vote
1answer
75 views

What is undefined in Mathematical Logic? A question that arises from negating a nested predicate.

Negate the following expression and indicate whether the negated statement is true. $$\forall x \in \mathbb{R}, \exists n \in \mathbb{Z}, x^n > 0 $$ Relevant equations De Morgan's Law for ...
0
votes
0answers
36 views

Not sure how a boolean algebra simplification step is done?

I've simplified a rather long boolean expression down to (where $'$ is $NOT$, $+$ is $OR$, and multiplication is $AND$): $f = b'd'+ad'+ac'+ab+bc'd$ But the simplest expression that I'm supposed to ...
0
votes
1answer
26 views

Demonstrate that (p → q) → ((q → r) → (p → r)) is a tautology.

I'm struggling to demonstrate that (p → q) → ((q → r) → (p → r)) is a tautology. I know that : ...
1
vote
1answer
26 views

Demonstrate that p ↔ (p ↔ q) ⇔ q

I know the answer is : (p ↔ p) ↔ q ⇔ q 1 ↔ q ⇔ q q ⇔ q But I don't understand why it isn't : ...
2
votes
1answer
26 views

Proof that no term (of a language of predicate logic) is a (non-empty) initial segment of another

I sense that the following simple argument is invalid, but cannot figure out why. Base Case: No variable or constant is an initial segment of a term, since the only terms that begin with variables ...
1
vote
0answers
26 views

How to prove/disprove tautologies using logic rules?

I'm given two statements and am trying to use logic rules to either prove or disprove if they are tautologies. First statement: $\neg(p \oplus q) \leftrightarrow (p \leftrightarrow q)$ Second ...
1
vote
0answers
27 views

Give complete derivation in natural deduction - My approach

Give a complete derivation in natural deduction of the following formula: $$((\varphi \rightarrow \psi) \rightarrow \psi) \leftrightarrow (\varphi \lor \psi)$$ My derivation I did the right ...
1
vote
0answers
25 views

Convert from sum of products to product of sums (Boolean algebra)

I had to simplify a boolean expression with a k-map then put it into a NOR-gate implementation circuit. I haven't made the circuit yet, but here is the work I've done: Original function: $$F(w, x, ...
1
vote
2answers
96 views

Equality in set theory

In Introduction to Axiomatic Set Theory by G. Takeuti and W. M. Zaring chapter 3 It is given: Definition of equality as: $a=b \Leftrightarrow (\forall x)[x \in a \Leftrightarrow x \in b]$. And it ...
1
vote
2answers
35 views

Can't find a logical formulation to this problem

In this problem are only truth tellers and liars. When meeting two people, A and B, you ask A: "Is any of you a truth teller?", to which A replies: "If B is a liars, then i'm a liar" What are A ...
-1
votes
0answers
25 views

What would this proposition be expressed in words? [duplicate]

How can this proposition $\forall$n$\in$N$\exists$m$\in$N n^4 = m^2 be expressed in words. Sorry my attempt is: For every natural number, n, there is an existential prime number that is an element of ...
0
votes
1answer
26 views

First order language and symbols

What is language? What is metalanguage? 3.What are symbols? Am I right in saying following: Any first order language consists of logical and non logical symbols. Where logical symbols consists ...
0
votes
2answers
43 views

What does this symbol of $\Longleftrightarrow$ mean?

What does it mean, is it an implication or does mean something else?
-1
votes
1answer
24 views

Formula Containing 4 Propositions

Give a formula containing exactly the propositions A, B, C and D, which is true if and Only if at most two of the four propositiins are 'True'
0
votes
2answers
17 views

Would this be a specific example of a tautology? $\neg p\vee(p\vee q)$.

I have an example, $\neg p\vee(p\vee q)$ would this proposition be considered a tautology according to the truth table?
1
vote
0answers
31 views

Questions on logic behind “proof by contradiction”

I'm trying to understand the logic behind "proof by contradiction" and hoping that I can clear up a few things in this post. First of all, suppose I have a proposition $P$ and from this I can imply ...
1
vote
1answer
22 views

Simplifying a Compound Statement

I have to simplify $\neg(s \wedge(t \vee u ) \wedge ((s \wedge t) \rightarrow u))$ I started by trying to using $(p \rightarrow q) \iff \neg p \vee q$ and DeMorgan's laws but things got messy. Any ...
0
votes
1answer
21 views

How to formulate this logic formula

The problem setting is very simple. Suppose we have three variables x, y and z and a constraints C/3 predicate that is satisfied by the three variables C(x,y,z), but C/3 might not be the only ...
0
votes
1answer
59 views

Predicate Logic Proof Question

I am struggling really hard with proofs I cannot seem to understand them at all no matter how hard i try. I'm thinking of getting a tutor because questions like this I just give up and fail on. Any ...
2
votes
4answers
61 views

How to prove $C$ from $A \leftrightarrow (B \leftrightarrow C)$ and $A \leftrightarrow B$?

How does one prove $C$ from the premises: $A \leftrightarrow (B \leftrightarrow C)$ and $A \leftrightarrow B$ ? I've tried to prove $C$ by contradiction, using a sub-proof which presumes $\neg ...
0
votes
0answers
12 views

Discrete math - logic [duplicate]

Can somebody please help me. How do I paraphrase this statement so that it doesn't have a negation anymore at all?
0
votes
2answers
29 views

Confused about how to use semantic tableau to answer questions of satisfiability

I'm taking a course in Mathematical Logic right now and we have to use semantic tableau to find out if a formula is satisfiable (some interpretations give a value of T). My question is: Given these ...
2
votes
1answer
48 views

A knights and knave problem involving a native with a speech disorder

On an island, every native is either a knight, who always tells the truth, or a knave, who always lies. You meet 4 natives, A, B, C, and D. This is what they say: A: "C is a knight iff D is a ...
0
votes
4answers
40 views

Logic - paraphrase propositions with negations to no negations

How do I paraphrase a proposition with a negation to not have a negation? I am thinking about this proposition
2
votes
1answer
61 views

Express $\forall n \in \mathbb N$, $\exists m \in \mathbb N$, $n^4 = m^2$ in words without using the symbol $\mathbb N$

Express $\forall n \in \mathbb N$, $\exists m \in \mathbb N$, $n^4 = m^2$ in words without using the symbol $\mathbb N$. My Solution: For all $n$ that is an element of Natural number there is ...
2
votes
2answers
48 views

How is the implication introduction used here?

I don't understand how the implication intruductions, the ones marked with the subscript $2 $ and $3 $ are used here. As I unerstand it, the implication introduction is used when we have a derivation ...
0
votes
3answers
29 views

Simplifying a logical compound statement

I need to simplify $(p \vee r) \wedge (\neg p \vee \neg r)$ (if possible and using the laws of logic) I tried to substitue $s: (\neg p \vee r)$ but that made it even worse. Can anyone suggest an ...
0
votes
1answer
35 views

Applying De Morgan's Law

I'm working on my assignment for Discrete Math and I'm not fully understanding how to do this question for it so I was wondering if anyone here could help show me how to do it properly; Use De ...
2
votes
2answers
27 views

How would I go from DNF to a simplified formula with less symbols?

Here's a DNF: $$(\neg A_1 \land \neg A_2 \land \neg A_3 ) \lor (A_1 \land \neg A_2 \land \neg A_3 ) \lor (\neg A_1 \land \neg A_2 \land A_3 ) \lor (\neg A_1 \land A_2 \land \neg A_3 )$$ And the ...
2
votes
0answers
54 views

Prove that $\Pi_{i \in I} \mathbf{A}_i \cong \Pi_{j \in J} (\Pi_{i \in I_j} \mathbf{A}_i)$ where $\{I_j \ | \ j \in J\}$ is a partition of I.

My problem is following: prove that $\Pi_{i \in I} \mathbf{A}_i \cong \Pi_{j \in J} (\Pi_{i \in I_j} \mathbf{A}_i)$, where $\langle \mathbf{A}_i \ | \ i \in I \rangle$ is an indexed set of similar ...
0
votes
2answers
69 views

How can i solve this logical problem?

This problem involves two people. Person A and person B. They can either always tell the truth, or always lie. When asked, person A replies that: "At least one of us is a liar". Does person A ...
0
votes
1answer
33 views

searching a number in 2D matrix

I was looking for algorithm on searching a number in a 2D matrix, with property that the matrix is sorted both row-wise and column-wise. Finally i came across, this link ...
0
votes
0answers
14 views

how to do classification of topological space which a poset is a frame

is module in algebraic geometry for classification of topological space which a poset is a frame which invariant is for doing this classification of topological space? if want to do full combination ...
1
vote
1answer
65 views

Showing associativity holds over n elements

Say we have a set $X$, with an associative binary operator $*$. How can we show that for any string $x_1 x_2 \ldots x_n$, when we insert brackets or the operation $*$, we will always get the same ...
-1
votes
0answers
12 views

Prove that, any formula occurring anywhere in another formula is a subformula. [on hold]

What could be the formal way of proving this definition for subformulas?
2
votes
1answer
30 views

Formal proof structure for $\forall n \in \mathbb{N}, P(n) \rightarrow \forall n \in \mathbb{N}, Q(n)$

I'm used to proving universal quantification claims (i.e. $\forall n \in \mathbb{N}, [P(n) \rightarrow Q(n)]$) by: Assuming an arbitrary number in the naturals, assuming the antecdent $P(n)$, doing ...
1
vote
1answer
62 views

$\neg P \lor P $ is always true.

$\neg P \lor P $. Why this statements is always true even if $P$ is undecidable statements . I can't understand it for $P$ undecidable in the other case I do ! help please ?
0
votes
1answer
28 views

how do i write a truth table for ∀n ∈ N, P (n) → P (n + 1).?

So i'm supposed to find a predicate such that: ∀n ∈ N, P (n) → P (n + 1) is true and write the truth table for it. So I chose the predicate: "11^n - 6 is divisible by 5 for every positive integer n". ...
0
votes
0answers
35 views

Let T(x,y) mean “x is a teacher of y”. What do the following statements mean? Are they true?

∃!yT(x,y) ∃x∃!yT(x,y) ∃!x∃!yT(x,y) ∃x∃y[T(x,y) ∧ ¬∃u∃v(T(u,v) ∧ (u≠x ∨ v≠y))] For the first one, is the meaning: There is one and only student that has teacher x? Am I on the right track with ...
0
votes
1answer
37 views

Determining if two statements are equivalent, logical sense.

I am confused, I am working with proofs and I have the following statement to work with $\forall n\in\mathbb{N},P(n) \implies P(n+1)$ I have a second statement $\forall n\in\mathbb{N}, ...