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)

0
votes
1answer
45 views

How to prove a valid argument? (discrete math)

"If I eat all night,then I can get fat.If I get fat then I will have a boyfriend.Therefore,if I eat all night, then I will have a boyfriend." Is the following a valid argument, according to what you ...
1
vote
2answers
57 views

Negate the statement in discrete math

I need help with the negation in discrete math The question is : Negate the statement and express your answer in a smooth english sentence. Hint first rewrite the statement so that it does not ...
0
votes
1answer
142 views

binary resolution rule proof

I want to proof the binary resolution rule that is, if we For any two clauses $C_1$ and $C_2$, if there is a literal $L_1$ in $C_1$ that is complementary to a literal $L_2$ in $C_2$, then delete $L_1$ ...
0
votes
2answers
58 views

finding shortest equivalent expression

I am trying to find the shortest equivalent expression of the following: ((C → D) $\wedge$ (D → C)) $↔$ (C $\wedge$ D ∨ ¬C $\wedge$ ¬D) I have "simplified" the expression into the following: (($\...
1
vote
1answer
56 views

functional completeness of $\{\to\}$ [duplicate]

Given that the set {∨, $\wedge$ , ¬} is functionally complete, how would I prove whether the set $\{\to\}$ is functionally complete? expressing $→$ in terms of $∨$: $¬A∨B$ expressing $→$ in terms ...
0
votes
1answer
41 views

Giving this formula in DNF and CNF propositional logic

The formula I am trying to turn into conjunctive normal form and disjunctive normal form is: $P \rightarrow (Q \land R)$ could anyone please help me give two answers, CNF and DNF? I have managed to ...
1
vote
2answers
35 views

$\forall x\in \left(0,\infty\right),\ \exists y\in\left(0,\infty\right)\ \text{ s.t. } xy = 1$

Prove if the statement is true $$\forall x\in \left(0,\infty\right),\ \exists y\in\left(0,\infty\right)\ \text{ s.t. } xy = 1$$ For the statement above, I argued that this ...
2
votes
1answer
90 views

Is math fool-proof? [duplicate]

I am an high school student, and I'm diving deeper and deeper into Maths, and thinking into studying it at university. I have read multiple books, and gazed at the beautiful proofs presented there. In ...
1
vote
1answer
99 views

proof of functional completeness of logical operators

If I know that the set of operators {∨, & , ¬} is functionally complete, how do I go about proving/disproving the functional completeness of the following set of operators? a) $\{\vee,\neg\}$ b) ...
1
vote
2answers
124 views

Prove that the set {→, ¬} is functionally complete

I am not sure how to do this question. I have looked at some of the other similar questions but to no avail I know that for a set of operators to be functionally complete, the set can be used to ...
0
votes
1answer
61 views

Is the size of the set created by the Kleene star always infinity? What about its closure?

My notes state $L^+$ denotes $LL^*$and is the closure of L under concatenation. That is, it is the smallest language that includes L and all strings that are concatenations of strings in L ...
1
vote
0answers
15 views

Linear Programming - Modelling Objective Function to Include Revenue as well as Cost

I am new to Linear Programming. The general two-variable problems I see have the objective function as maximizing profit. However, what if there is a cost per unit of each variable? Example: I have ...
-3
votes
1answer
44 views

First-Order Structure Logic

M is a model with domain M(∀) = {1, 2, 3} and • M(a) = 1, M(b) = 3, M(c) = 2 • M(P) = {1, 3}, M(R) = {(3, 1),(2, 2),(2, 1),(3, 3)} h is a variable assignment with h(x) = 2, h(y) = 3, and h(z) = 2. ...
0
votes
2answers
40 views

Formal Proofs of Logic

I need to give Fitch-style formal proofs for the following: 1) Premises: ∀x∀y∀z((R(x, y) ∧ R(y, z)) → R(x, z)) ∀x∀y(R(x, y) → R(y, x)) To prove: ∀x∀y(R(x, y) → R(x, x)) 2) Premises: ∀x(P(x) → ...
1
vote
1answer
74 views

How is the following statement for true for this condition? [closed]

Let f be some function for which you know only that if $0 \lt \mid x-3\mid \lt 1$, then $\mid f(x)-5 \mid \lt 0.1$ How is this statement necessarily true? ' If $\mid x-2.5 \mid \lt 0.3$, then $\mid ...
0
votes
1answer
17 views

∀x ∈R, ∃y ∈R s.t ∀z ∈R , x + y = z

∀x ∈R, ∃y ∈R s.t ∀z ∈R , x + y = z The above statement is false but I can't figure out why? Or how can I prove that the statement is false?
0
votes
1answer
43 views

Showing extensionality for Mostowski collapse

I have been trying to show that if $\gamma$ is such that there is a real (an element of $2^\omega$) in $L_{\gamma+1} \setminus L_\gamma$, then there are countable $M$ and a surjection $f : \omega \...
0
votes
2answers
24 views

{2} ⊆ P({2,3}) vs {{2}} ⊆ P({2,3})

{2} ⊆ P({2,3}) - False {{2}} ⊆ P({2,3}) - True Why is that the case above? I've tried analyzing it, and it came to this, For the 1st statement, they are claiming that {2} is a subset of P({2,3}. ...
1
vote
3answers
72 views

If an empty set is an element of a set, $\{5,\{\}\}$ is that equal to just $\{5\}$?

Is this true $\{5, \emptyset\} = \{5\}$? I know that the empty set is always a subset of any set, but when it's an element is that necessary to write in or not?
0
votes
2answers
49 views

What is the distinction being made with regards to truth and falsity in these two sources?

I'm currently studying logic and i'm confused about the truth or falsity of statements within an argument. From Daniel J. Velleman's, How to Prove It, pg.9: "Although we have no guarantee the ...
1
vote
0answers
16 views

A preordered set related to realisability logic

Let $\Lambda$ be any partial combinatory algebra. For each set $X$, define a binary relation on $\mathscr{P} (\Lambda)^X$ as follows: Given $P, Q : X \to \mathscr{P} (\Lambda)$, $P \le_X Q$ iff ...
0
votes
1answer
43 views

Showing that a certain formula of second order logic with full semantic is true in all and only non-standard model of arithmetic.

Showing that a certain formula of second order logic with full semantic is true in all and only non-standard model of arithmetic. $\exists X(\exists x Xx \wedge \forall x\forall y((Xx \wedge (x=0 \...
1
vote
3answers
65 views

How it can be formally proved that a formula of First Order Logic with identity has only infinite models?

I have an irreflexive and transitive relation $R$. Then I want to prove that $\forall x \exists y (xRy)$ has only infinite models. I have an intuitive idea for which the relation $R$ cannot be ...
1
vote
2answers
153 views

Real numbers for beginners

I am thinking about the Wikipedia (I understand disputed) article about “definable real numbers”. It begins to say that, A real number $a$ is first-order definable in the language of set theory, ...
0
votes
0answers
32 views

Relations and logic

$R$ is a relation defined on the set $\mathbb Z$ of integers. For any $a,b \in \mathbb Z$, $a\,R\,b$ iff for any prime number $p$,one has $p\,|\,a$ if and only if $p\,|\,b$. I'm trying to prove or ...
0
votes
1answer
59 views

Determine the truth value for the predicate (logic)

Im not quite sure how to go about answering these type of questions as the difference of the universal and existential quantifier are confusing me. Hoping someone could explain how to go about ...
1
vote
0answers
46 views

how to determine if formula satisfies without creating a truth table

$(p \wedge q \wedge r) \wedge (\neg p \vee r)$ So far, what I have got is that $(p \wedge q \wedge r)$ satisfies because if $p$, $q$ and $r = 1$ then $(p \wedge q \wedge r)$ also $= 1$. For $(\neg p \...
1
vote
0answers
31 views

Find interpretations of formulas

Consider the structure $A=<\mathbb{N},<;\cdot,1>$. Find the following interpretations of formulas (for an arbitrary valuation v): (c) $[\![ \forall x_1\exists x_1 P(x_1,x_2) ]\!]$ (d) $[\![ ...
0
votes
1answer
95 views

JAPE double negation handling

I'm trying to prove a simple conjecture using JAPE application. There must be some 'magic trick' in JAPE to get rid of double negation statements but I have no idea how to handle it properly. The ...
0
votes
3answers
56 views

In logic why can't “p unless q” be “q -> ~p”?

Logically, when I think about p unless q I want to say that it is equivalent to q -> ~p, but the only equivalence is ...
0
votes
0answers
26 views

theory of semi-algebraic sets

Is there a formal axiomatic way to study semi-algebraic sets? Some facts about them can be deduced by their polynomial structure. Semi-algebraic sets are closed under compliments, intersections, ...
0
votes
1answer
34 views

Determine the truth value of these predicates:

The domain for x, y, z is real numbers. i) $\forall x \exists y (y^2<x)$ FALSE counterexample: $x=0$ ii) $\forall x \exists y (y^3<x)$ TRUE iii) $\forall x\exists y \forall z ((y>0) \...
0
votes
1answer
40 views

Simplifying (P AND Q) OR (NOT P AND NOT Q) [closed]

Can that expression be more simplified or is it already in it's simplest form?
1
vote
0answers
49 views

Translating a sentence in a quantified statement

How would you write the following proposition as a quantified statement? "There are no birds that belong to anyone but me" Assume the following boolean functions: $B(x)$ (Is $x$ a bird?), $O(...
-1
votes
1answer
36 views

Can we do the inductive step without using inductive hypothesis

I wonder if in case I correctly performed first step of induction and next I proved it for n+1, this is still Mathematical Induction? I know, that if I proved it without inductive hypothesis, I could ...
0
votes
1answer
76 views

Proof completion problem: I can only use primitive rules of inference, and I have contradictory premises.

Standard proof completion: ~(p&q) A ~(~p&q) A ~(p&~q) A ~(~p&~q) A SHOW r Contradicting r and then showing a contradiction seems like the obvious plan of attack, but after that I'm ...
0
votes
2answers
30 views

Is a logical disjunction statement reversible?

This might be a stupid question, but I'm just learning proofs so I'm unsure. if I have $e \vee f$, can I change it to $f \vee e$ without repercussion?
0
votes
2answers
27 views

If $A \subseteq B$, then prove by using laws of logic that $(A \times B) \cap (B \times A) = A^2$

I think I know the first step but I need some hints on how to complete it. Let, $(x,y)$ is an element of $(A \times B) \cap (B \times A)$
0
votes
1answer
39 views

What do I need to learn as prerequisites for logic programming in miniKanren or Prolog?

I'm interested in logic programming for AI. Can I just learn logic programming without any math knowledge? If I couldn't, what do I need to learn?
1
vote
0answers
54 views

Do we consider the dual concept of the sheaves?

The concept of a sheaf on a topological space X can be veiwed as a projection from a topological E space to X which is a local homeomorphism (it belongs to the category of topological spaces). What's ...
1
vote
1answer
110 views

BAN logic notation: what does horizontal line mean?

I'm learning BAN logic and trying to understand the notation. The bellow picture is an example form Security Engineering by Ross J Anderson. My question is what does the horizontal line mean? I'm ...
1
vote
1answer
31 views

Will assuming an undecidable statement result in a consistent system?

If you assume that an undecidable statement in a consistent axiomatic system is true (or false), will that new system also be consistent? For example, does $\mathsf{ZF}$ being consistent imply that ...
1
vote
1answer
60 views

Proof by contradiction/contrapositive

I'm just trying to make sure I have this right: (b) Give a proof by contradiction of: “If n is an odd integer, then n 2 is odd.” $n = 2k-1$ $n^2 = (2k-1)^2$ $a = n$ is odd $b = n^2$ is odd Since ...
0
votes
1answer
37 views

Prove that $\overline{A\cap B \cap C}=\overline{A}\cup(\overline{B}-\overline{A})\cup \overline C$

How do you prove $\overline{A\cap B \cap C}=\overline{A}\cup(\overline{B}-\overline{A})\cup \overline C$? The only thing that seems clear to me is by deMorgan the LHS breaks down to $(\overline A \...
1
vote
2answers
31 views

If a c.e. set $X$ is such that every $\Sigma^0_2$ set is c.e. in $X$, then $X \equiv 0'$

Is it true that if a c.e. set $X$ (of naturals) is such that every $\Sigma^0_2$ set $Y$ is c.e. in $X$, then $X \equiv 0'$? An obvious and naive trial to prove this would be to take $Y := 0''$. ...
0
votes
2answers
37 views

How to prove arguments with rules of inference?

I have the following argument: -∀x(P(x) ∨ Q(x)) ∀x(¬P(x) ∧ Q(x)) → R(x) ___________________. ∴ ∀x(¬R(x) → P(x)) I don't want the answer. I just need some general tips to get there. I know I can ...
1
vote
1answer
74 views

proving a binary operation is well-defined.

Theorem 4 of Landau's "Foundations of Analysis" defines sum of two numbers. He fixes one argument and prove it for the other and vice versa. I want to know why we can do this. I think the proper way ...
1
vote
4answers
34 views

How do you read this logical statement and verify its truth value? Nested quantifiers

$\forall x\exists y \forall z ((y>0) \land ((z^2<y) \rightarrow (z^2+1<x^4)))$ And also how would you verify quantifier claims over a domain, ie. reals? I previously have been doing these ...
2
votes
1answer
64 views

How to give a formal proof for $ \exists \space x\space \forall \space y(P(x) \rightarrow P(y))$ in fitch

To practice for my exams, my teacher gave us several exercises to practice but didn't supply us any answers. Now after looking at this problem for 2 nights I have no idea left on how to solve it. If ...
0
votes
1answer
43 views

Give formulas whose interpretations in the model represent the predicates

sorry for this really stupid question. Consider the structure $A=<\mathbb{N},<;\cdot,1>$ (arity type $<2;2,0>$). Give formulas whose interpretations in the model represent the ...