Questions about mathematical logic, including model theory, proof theory, computability theory (a.k.a. recursion theory), and non-standard logics. Questions which merely seek to apply logical or formal reasoning to other areas of mathematics should not use this tag. Consider using one of the ...

learn more… | top users | synonyms (1)

32
votes
15answers
5k views

Is it true to say that “it's not logically possible to prove something can't be done”?

A friend of mine asked me if I could explain this statement: "It's not logically possible to prove that something can't be done". The actual reason is the understanding of this strip: Since I'm ...
0
votes
1answer
159 views

Demonstrating seconds Morgan's law using the first one and double negation

These are the 2 Morgan's laws: 1. NOT(A ^ B) = NOT(A) v NOT(B) 2. NOT(A v B) = NOT(A) ^ NOT(B) This is the double negation law: ...
1
vote
3answers
139 views

Prove that $2^{1/2}$ is irrational

I'm trying to understand each part of this completed proof that my professor did, here is my interpretation in parentheses, please advise as necessary. Proof: Assume that $2^{1/2}$ is rational, then ...
1
vote
1answer
68 views

Can this logic expression be further simplified?

I am learning logic at faculty and of course it causes a little bit of confusion sometimes. $P \lor \neg Q \lor (P \land \neg R)$ Am I forgetting a law (probably yes)?
0
votes
1answer
56 views

Logistic Maps Homework Help

Consider the logistic map $G(x) = 4x(1-x)$. Let $q_0=0<q_1<q_2<q_3...<q_7$ be the eight points left fixed by $G^3$. Determine which are the two fixed points and which other points are ...
2
votes
2answers
888 views

Modus Ponens Proof

I have written the truth table for all of the forms of $P$ and $Q$.Then maintained the table to find $P \rightarrow Q $ and $[(P \rightarrow Q) \wedge P]$.As we know, we can write arguments in forms ...
4
votes
1answer
72 views

Questions using If/Then and IFF

I'm having some trouble with statements of the form "if/then" vs "if and only if". Would someone mind giving me a sanity check here? My interpretation does not seem to make a lot of sense. Let ...
2
votes
2answers
66 views

Another question on a 2-player game strategy

This is a 2-player game. The game begins with a binary string (leading zeros not ignored). Each turn, a player can remove a sequence of consecutive and identical digits from the left. For example, ...
5
votes
1answer
626 views

Game of dots: winning strategy?

The game begins with a row of $n$ numbers, in increasing order from $1$ to $n$. For example, if $n=7$, we have a row of numbers $(1,2,3,4,5,6,7)$. On each turn, a player must either remove 1 number, ...
0
votes
2answers
35 views

Write out a simplified SOP expression for a function

$0 \space 1 \space 2\space 3\space 4\space 5\space 6\space 7 \\ 15\space 14\space 13\space 12\space 11\space 10\space 9\space 8\space \\ 16\space 17\space 18\space 19\space 20\space ...
0
votes
1answer
60 views

Can anybody explain this logical symbol?

I know this is not right place to post this question. Please help me I will notate & for "and" and ^ for "or" [Editor: Instead, let's use MathJax to notate $\land$ for "and" and $\lor$ for ...
2
votes
3answers
73 views

Argument with a friend over correct prepositional logic for a sentence

It is possible that Clinton or Sanders and possibly Bush may run for President. we both agreed on the assignment of prepisitional variables: P = It is possible that Clinton may run for President q ...
0
votes
2answers
348 views

Strengthening the Consequent: From A implies B, infer A implies (B ^ C).

Strengthening the Consequent: From A implies B, infer A implies (B ^ C). How do I construct a Fitch style proof to prove this?
1
vote
2answers
232 views

Using logical Properties to prove a tautology

So I have to prove this as a tautology. I've been stuck on this forever and am not sure where to go. I experimented and got this far, and looking for some pointers on where to take it next. (p → q) ...
1
vote
2answers
51 views

Order of parameters in quantified predicates

I'm studying up for my midterm in Discrete Math and I've been looking at sample questions and their solutions. There is one I don't really understand and I was hoping someone could help me out. ...
2
votes
1answer
93 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
191 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 ...
4
votes
1answer
167 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
2k views

Verify Demorgan's Law Algebraically

If $\overline X \equiv \text { not }X$, De Morgan's Laws are stated as: $ \overline{(A + B)}= \overline A\cdot \overline B$ $ \overline{(A\cdot B)} = \overline A + \overline B$ Verify the above ...
1
vote
1answer
72 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
112 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 ...
1
vote
0answers
37 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 ...
11
votes
1answer
2k 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
93 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
95 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
67 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' ...
2
votes
1answer
143 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
1answer
45 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
145 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
67 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
322 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
108 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
59 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 ...
0
votes
1answer
63 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
71 views

What does this symbol of $\Longleftrightarrow$ mean?

What does it mean, is it an implication or does mean something else?
0
votes
2answers
23 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
95 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
43 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
39 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
173 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
97 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 ...
1
vote
2answers
986 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
136 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
62 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
69 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
86 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
117 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
319 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
259 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 ...
3
votes
0answers
94 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 ...