Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

в) Зх VyP(x) &Q(y)=> VxR(x) ; г) ВхВуР(х,у) &Q(z); д) VzP(z) &BxQ(x,z) ^ByR(z,y) vQ(z,x) ; e) ByP(x,y) &Vx(x,z) =^P(y,y). 17. Каждый из следующих предикатов, определенных на множестве всех действительных чисел, превратите в высказывание: 1) подставляя вместо свободной переменной какое-либо ее значение; 2) связывая свободную переменную каким-либо квантором. Определите истинностные значения полученных высказываний. а) Vx(x+y=y+x); ^)х>у; в)ху=5; т) Зс(ху=5); д)х^+у^^; е) \/x^(x+y=z); ж) Vx(sinx>l)^(x <0); з) Зс(х>у). 18. Пусть приводимые ниже предикаты определены на множестве всех действительных чисел. Изобразите графически области изменения свободных переменных, при которых следующие предикаты принимают значение И: а)у>х^; б) \/x(y<smx); в) Зс(х^+у^<4); г) \/y^(sirvc =1); д) Vx(x^+4y^<4); е) Vy(x + ^ту <2). 19. 1) Истинна, ложна или выполнима A(fi (f2 (x,y)),y) в каждой из следующих интерпретаций: а) М=(0, оо), А(х,у): х=у, f2(x,y): х+у, fi(z): Inz] A(x,y): х=-у, f2 (x,y): ху, fi(x): х^; A(x,y): х^у, f2(x,y): 1/х+у, fi(x): х ; 2 б) М=(0,2ж] ъ)М=(0,1], т) М=[0,2л:], А(х,у): х'^=-у, f2(x,y): х+у, fi(x): sinx. 2) Истинна, ложна или выполнима формула VxA(fi(x,y ),f2 (fi(x,y))) в интер­ претации: М=(- оо, oo);f2(z): z^;fi(x,y): x+j/; A(x,y): x=y. 20. Предикат A(x,у) задан на множестве М=/7,2,5/ таблицей. 20. Предикат (Ос,задан на множестве М= 2,5^ таблицей X \ у 1 2 3 1 И И и 2 Л л и 3 и л и Определите истинностное значение приводимых далее формул при каждом значении свободной переменной: а) \/xA(x,yJ; 6) 3cA(x,yJ; в) \/yA(x,yJ; r)^A(x,yJ. 21. Пусть М={1,2,3} и на этом множестве М заданы предикаты А(х,у) и В(х) таблицами: В(х): А(х,у): X \ у 1 2 3 1 Л И л 2 и л и 3 л и л X В(х) 1 Л 2 и 3 л Определите истинностное значение формул: а) ЗсА(х,х); б) VxA(x,x)^BxVyA(x,y)\ в) БхБу(В(х)&А(х,у)\ г) (БхВ(х))&\/х1А(у,у)\ 55