0
votes
1answer
38 views

Solving a version of the liar paradox

Given two people $Alice ,Bob$ are either lying or telling the truth Now suppose $Alice$ says "At least one of us is lying." We have two cases: $Alice$ is telling the truth $\implies$ $Bob$ is ...
1
vote
1answer
24 views

Tranlsation of english to nested quantifiers and forming their negations

You are given the following propositional function: B(x,y): Writer x has written a book on subject y. The domain for x is all people in the world, and the domain for y is all subjects in the world. ...
0
votes
4answers
46 views

Island of knights and knaves

This question is about an island of knights and knaves, where knights always speak the truth and knaves always lie. You encounter two people A and B. Determine, if possible, what each of them are if ...
0
votes
2answers
57 views

Quantified Logic with miltuple variables

Problem: ∀y¬∃x¬(¬Fxy ∨ Fyx) ⊢ ∀y∀z(Fyz→Fzy) I don't really understand how to deal with multiple variables in instances like this. So far I have: ...
2
votes
0answers
54 views
+50

3-Coloring a graph using propositional formulas

Hello everyone I am studying for an exam on logic and computability, I am trying to tackle a specific problem so any help would be greatly appreciated: Let $G = (V,E)$ be an undirected graph ...
0
votes
1answer
43 views

Implication or Bidirectional in “x is a Prime”

I have a question regarding First Order Logic. I have to express the property "x is a Prime" in First Order logic. So far I have the following solution: $\forall x\;Prime(x) \leftrightarrow \neg ...
1
vote
1answer
51 views

Finding Truth Values Of Nested Quantifiers

I'm looking at for example, $∃x∀y,P(x≥y+1)$ I'm told in order to prove that this is true I can us the technique that follows: Find one value of $x∈X$(only needs to be one) that has the property that ...
3
votes
1answer
64 views

Size of topological space depending on the size of local basis. (With elementary submodels)

Recall that the character of a topological space $\chi(X)$ is the minimum cardinal $\kappa$ such that every point in $X$ has a local basis of size $\kappa$. I need to prove that if $X$ is compact ...
1
vote
1answer
39 views

Proof by induction of propositional formulas

I have two inductively defined operations: $\text{bin}$ base case: If $p$ is a propositional letter, then $\text{bin}(p) = 0$ inductive step $\text{bin}(\neg \phi) = \text{bin} (\phi)$ ...
0
votes
1answer
34 views

Boolean Function question [duplicate]

I need to know how I can prove this question. Prove that not every boolean function is equal to a boolean function constructed by only using And ($\wedge$) and Or ($\vee$)
1
vote
1answer
52 views

$\Sigma \ \vdash A \lor B \ \ $

I'm stuck with the following question: prove or disprove the following: if $\Sigma \ \vdash A \lor B \ \ $ then $\ \ \Sigma \ \vdash A \ \ $ or $\ \ \Sigma \ \vdash B $ ...
1
vote
1answer
67 views

Predicate Calculus English Translation

I'm having difficulty translating the following English sentences into predicate logic. Any help would be greatly appreciated. $B:\qquad$_ is a book $A:\qquad$_ is an author $H:\qquad$_ is a ...
2
votes
1answer
24 views

Equivalent formula in countable structures

Question, if two sentences A & B, are such that for all countable structures M: M⊨A iff M⊨B, and A & B be thus logically eguivalent. But how?! I understand that I have to use ...
0
votes
2answers
71 views

How many Scythians were there?

I was doing a maths test yesterday and the last question on the exam was as follows: $2500$ years ago, a Scythian king called Ariantas ordered every one of his subjects to bring him an arrow head. ...
2
votes
1answer
38 views

compound proposition logically equivalent

I can not solve this question Find a compound proposition logically equivalent to $p \to q$ using only the logical operator $\downarrow$.
1
vote
1answer
40 views

Subtraction of elements from $\mathbb Z$

Let $M_n$ be the set of integers which are integer multiples of $n$. If $\mathbb N = {1,2,3...}$ What would $$ \mathbb Z - \bigcup_{n\in\mathbb N}M_{2n+1} $$ be? I know that $M_{2n+1}$ represents ...
0
votes
2answers
21 views

negation of powersets

If given two power sets P(A) and P(B), and told that the Union of these two sets was a subset of another powerset P(C), what would be the negation of this statement? Would the Union go to an ...
0
votes
2answers
30 views

Use of “for all” in definition of reflexive and symmetric relations.

My book says that a relation R on A is reflexive, if $\ (a,a) \in R, \ for\ every \ a \in A$ symmetric, if $\ (a_1,a_2) \in R \implies (a_2,a_1) \in R,\ for\ all\ a_1,a_2 \in A$ Although I ...
0
votes
1answer
48 views

Checking Boolean Algebra work - Simplification

I am currently working on an assignment for a CE class I am taking, and I wanted to know if I have been simplifying these equations correctly. I'm supposed to reduce them to a sum of products. 1) ...
1
vote
2answers
66 views

Discrete Maths Logic Question

p = False, q = True and r = False. Is $¬(p∨q)∧(¬p∨r)$ = false? My reasoning: $$(p∨q)=T \text{ as it is (F or T)}$$ but its the negation so $¬(p∨q)=F$? Then, $(¬p∨r)$ as p is F but its the ...
1
vote
1answer
57 views

Answering questions with truth tables

"With every dinner I have three rules": If I don't drink wine, then I eat soup If I eat soup and drink wine, then I'll have some pudding If I have pudding or don't drink wine, then I'll skip the ...
0
votes
1answer
69 views

Sound and Complete

So I am in a introductory formal logic class, and my professor has asked us questions on our homework about "Sound and Complete rules of inference". Unfortunately, I am having a hard time finding out ...
0
votes
2answers
53 views

Some QL Translations

So here I am again... Still stumped, with little progress made. Please help me translate the following sentences to QL. Anyone who knows everyone Alma knows knows Alma Everyone who knows everyone ...
1
vote
1answer
40 views

Translations with more than one quantifier

I've been having trouble translating statements with multiple quantifiers, and I would like some feedback and advice on my answers for the following translations. Let $Kxy$ mean x knowns y. Some know ...
0
votes
1answer
25 views

QL Translation Question

I was attempting to translate the statement "All love all.", and then check if it is a logical truth. I first want to know if my translation is correct. Let $Lxy$ mean x loves y,then $\forall x ...
1
vote
0answers
78 views

Validity of three syllogisms with venn diagram

me and my study group are struggling with a "how to proof syllogism conclusions" approach. We got three syllogisms which look like the following: We know for a fact that syllogism #1 and #3 are ...
4
votes
1answer
61 views

A couple of Natural Deduction proofs

I have two proofs that I can't figure out how to get started on. a) q ├ (p ∨ ¬p) & q b) p ∨ q, p→¬q Ⱶ (p→q)→(q ∧ ¬p) for q ├ (p ∨ ¬p) & q I only assumed that I might try to prove it ...
2
votes
1answer
77 views
2
votes
1answer
40 views

formal proof - logic

I am trying to prove the following, using natural deduction: $$p\wedge q\Leftrightarrow p \vdash p \Rightarrow q$$ with the following but i seem to get stuck. I know i have to prove $q$, but am not ...
1
vote
1answer
90 views

Prove $\forall x~\forall y~\forall z (x+y)+z=x+(y+z), \forall x~\forall~y\exists z~ x=y+z, \forall x~\forall z \exists y x=y+z ⊢ ∃y∀x x+y=x$

I need help using the standard rules of predicate logic with quantifiers to prove $~\forall x~\forall y~\forall z ~~(x+y)+z=x+(y+z), ~\forall x~\forall y~\exists z ~~x=y+z, ~\forall x~\forall z~ ...
0
votes
1answer
48 views

Mathematical Induction for greedy algorithm problem?

Suppose you want to place towers along a straight road, so that every building on the road receives cellular service. Assume that a building receives cellular service if it is within one mile of a ...
0
votes
1answer
96 views

Propositional calculus proof must involve instance of $(\neg \neg p \Rightarrow p )$

Hi this is a question about propositional calculus. The axioms I am working with are: $(p \Rightarrow (q\Rightarrow p))$ $ ((p \Rightarrow (q \Rightarrow r)) \Rightarrow ((p \Rightarrow q ) ...
0
votes
3answers
40 views

Predicate Logic, confusion about implication statement.

Let's say the domain of discourse is the set of 10 balls, numbered as such from 1 to 10. Some (more than 1 but NOT all) of those balls are put into a bag, and then some of those in the first bag are ...
2
votes
1answer
44 views

How do I use rules of inferences to imply a conclusion from 4 premises?

I am a little confused on how to use 4 premises to prove a conclusion. Can you please tell me if my logic is sound for the following proof: ...
-1
votes
2answers
50 views

Formalizing sentences in predicate logic

I would like to formalize "The lecturer is happy, if all his students love logic" using Lecturer as a constant; $H(X) = X$ is happy; $S(X) = X$ is a student; $L(X) = X$ loves logic; $T(X,Y) = X$ ...
0
votes
3answers
77 views

Rewrite expressions

I have to prove that $$q\lor(¬q\land(p\lor q))$$ is equal to just $q$. This is normally done with logical equivalences, but I can't solve this one. Can somebody please help? ...
1
vote
3answers
95 views

Is -1 less than 0.1?

In a High School Maths Test, I presumed that since -1 has as much mathematical mass as a whole unit [-1 x -1 = 1, 1 x 1 = 1] and 0.1 represents one tenth of a unit, that -1 is greater than 0.1 -1 is ...
1
vote
2answers
68 views

A quick question about a logical negation

I just want to make sure I'm negating the following logical statement correctly (for a contradiction proof): For every set $A$, there exists a well ordered set $V$ such that there exists no ...
0
votes
1answer
36 views

Determine whether each of the following sets is well ordered?

A set is well ordered if every nonempty subset of this set has a least element. Determine whether each of the following sets is well ordered. a) the set of integers b) the set of integers greater ...
2
votes
1answer
37 views

Every truth function of the inderterminates X and Y is an iterated composition of negations and disjunctions.

I'm reading K.T.Leung and Doris L.C.Chen's Elementary set theory.I can't solve exercise 10: Prove that every truth function of the inderterminates X and Y is an iterated composition of negations and ...
0
votes
1answer
45 views

What is the proper way to format a hypothetical syllogism proof?

Problem: Show that these three statements are equivalent, where $a, b \in R:$ (i) $a < b$, (ii) the average of $a, b,$ is greater than $a,$ and (iii) the average of $a$ and $b$ is less than $b$. ...
0
votes
1answer
55 views

Elementary Truth Functional Logic question

So I am currently attacking a question from the first chapter of my logic book. I know that the question is true, but I am having a hard time actually proving it. The question is as follows. If a ...
0
votes
1answer
38 views

Completeness of posets

I think this is rather a simple question in order theory, but if someone could explain it step by step that would be really useful. If we have an arbitrary set, then let's denote the set of all finite ...
1
vote
2answers
65 views

Are the following statements correctly translated?

Using predicate symbols shown below and appropriate quantifiers, write each English language statement as a predicate wff. Domain is all the objects in world. B(x) : x is a bee F(x) : x is a ...
1
vote
3answers
82 views

Constructing Logical Proofs — Only one premise?

Alright, so I've been staring at this problem for two hours trying to figure out what exactly is wrong. Is there a typo? Am I missing something? Here is the problem: $A$ /∴ $B \rightarrow (\lnot ...
1
vote
2answers
71 views

Question about quantifier logic

This is my first post on the mathematics stack exchange so please bear with me.. I am new to quantifier logic and I just can't seem to wrap my head around it. I have been given four statements and I ...
0
votes
1answer
59 views

Logic: How to find a c-variant of a quantified formula in an interpretation?

Taken from Daniel Bonevac's Deduction Introductory Symbolic Logic, page 194: Let D = $\{ a \}$, $[a] = a$, $[F] = \{ a \}$, and $[R] = \{ <a, a> \}$. What is the truth value of these formulas ...
1
vote
1answer
28 views

Hasse graph of a poset.

Let $S = \{a, b, c, d, e, f\}$. The graph of a poset $(S,\lesssim)$ looks like this: Except vertices of the graph in my textbook are represented by letters. The letters correspond to the numbers in ...
1
vote
2answers
89 views

Prove $A+(B+C) = (A+B) +C$ using the definition of $A+B$

Let $A$ and $B$ be sets. Define the symmetric difference of $A$ and $B$, written $A+B$, by $A+B=(A \cup B) \backslash (A \cap B)$. Prove the following statement: f.$A+(B+C) = (A+B) +C$ We need to ...
0
votes
2answers
71 views

Help with really confusing venn diagram

So this is by far the most confusing venn diagram problem i've ever done. Can someone help me out? I know that Real numbers contain rational, and rational contain integers, but i get really confused ...